using System;

public class Program

{

    public static void Main()

    {

        int [] array = {3,4,5,6,1,2};

        int key = Find(array,9);

        Console.WriteLine(key);

    }

    public static int Find(int [] array, int key)

    {

        int pivotIndex = FindPivot(array);

        int keyAtIndex = 0;

        if(array[pivotIndex] == key)

            keyAtIndex = pivotIndex;

        else if(pivotIndex == -1)

        {

            keyAtIndex = BinarySearch(array,0, array.Length-1, key);

        }

        else if(key > array[0])

        {

            keyAtIndex = BinarySearch(array,0,pivotIndex-1, key);

        }

        else if(key < array[0])

        {

            keyAtIndex = BinarySearch(array,pivotIndex+1,array.Length-1,key);

        }

        return keyAtIndex;

    }

    public static int FindPivot(int []array)

    {

        for(int i=1; i<array.Length; i++)

        {

            if(array[i] <array[i-1])

                return i;

        }

        return -1;

    }

    public static int BinarySearch(int [] array, int low, int high, int key)

    {

        while(low <= high)

        {

            int mid = low + (high-low)/2;

            if(array[mid] == key)

                return mid;

            else if(array[mid] < key)

            {

                low = mid+1;

            }

            else if(array[mid] > key)

            {

                high = mid-1;

            }

        }

        return -1;

    }

}