import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        //找到k
        int k = findK(nums) ;
        //先还原数组(三次反转)
        reverse(nums , 0 , k - 1) ;
        reverse(nums , k , nums.length - 1) ;
        reverse(nums , 0 , nums.length - 1) ;
        //二分查找
        int idx = binarySearch(nums , 0 , nums.length - 1 , target) ;
        //坐标映射(将原数组中的元素位置映射成旋转后的数组的位置)
        return idx == -1 ? -1 : (idx + k) % nums.length ;
        
    }
    //二分查找
    public int binarySearch(int[] arr , int s , int e , int t) {
        while(s <= e) {
            int m = s + (e - s) / 2 ;
            if(arr[m] == t) {
                return m ;
            } else if(arr[m] < t) {
                s = m + 1 ;
            } else {
                e = m - 1 ;
            }
        }
        return -1 ;
    }
    //找到旋转数组的分界点
    public int findK(int[] arr) {
        for(int i = 0 ; i < arr.length - 1 ; i ++) {
            if(arr[i + 1] < arr[i]) {
                return i + 1 ;
            }
        }
        return 0 ;
    }
    //在s-e的范围翻转
    public void reverse(int[] arr , int s , int e) {
        while(s < e) {
            int t = arr[s] ;
            arr[s] = arr[e] ;
            arr[e] = t ;
            s ++ ;
            e -- ;
        }
    }
}