import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	// assuming ascending order a[0] <= a[1]
    public static int find_first_index (int [] arr)
    {
        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] > arr[(i+1) % arr.length])
            {
                return (i+1) % arr.length;
            }
        }

        return 0;
    }
	
	public static int startSearch(int a[], int x)
	{
		int f = find_first_index(a);
		
		return search(a, f, 0, (a.length-1), x);
	}
	
	public static int search(int a[], int f, int left, int right, int x)
	{
		int s = a.length;
	    int mid = (left + right) / 2;
	    if (x == a[(mid+f)%s]) { // Found element
	        return mid;
	    }
	    if (right < left) {
	        return -1;
	    }
	
	    /* While there may be an inflection point due to the rotation, either the left or 
	     * right half must be normally ordered.  We can look at the normally ordered half
	     * to make a determination as to which half we should search. 
	     */
	     
	    if (a[(left+f)%s] < a[(mid+f)%s]) { // Left is normally ordered.
	        if (x >= a[(left+f)%s] && x < a[(mid+f)%s]) { 
	            return search(a, f, left, mid - 1, x);
	        } else {
	            return search(a, f, mid + 1, right, x);
	        }
	    } else if (a[(mid+f)%s] < a[(left+f)%s]) { // Right is normally ordered.
	        if (x > a[(mid+f)%s] && x <= a[(right+f)%s]) {
	            return search(a, f, mid + 1, right, x);
	        } else {
	            return search(a, f, left, mid - 1, x);
	        }               
	    } else if (a[(left+f)%s] == a[(mid+f)%s]) { // Left is either all repeats OR loops around (with the right half being all dups)
	        if (a[(mid+f)%s] != a[(right+f)%s]) { // If right half is different, search there
	            return search(a, f, mid + 1, right, x);
	        } else { // Else, we have to search both halves
	            int result = search(a, f, left, mid - 1, x); 
	            if (result == -1) {
	                return search(a, f, mid + 1, right, x); 
	            } else {
	                return result;
	            }
	        }
	    }
	    return -1;
	}
	
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
}