Given an array that is sorted, but after sorting some elements are moved to either of the adjacent positions, i.e., arr[i] may be present at arr[i+1] or arr[i-1]. Write an efficient function to search an element in this array. Basically the element arr[i] can only be swapped with either arr[i+1] or arr[i-1].
For example consider the array {2, 3, 10, 4, 40}, 4 is moved to the next position and 10 is moved to the previous position.Input Format
Integer N followed by N elements of the nearly sorted array. Integer target representing the element to be searched.
Output Format
Print the index of the element if found, else -1.
Constraints
Number of Elements in Array <= 10^6. All the elements in the array will be distinct.
Notice
Binary Search
Example
Input
7 10 3 40 20 50 80 70 40
Output
2