private int searchin(int[] A, int left, int right, int target) {
        int mid = (left + right) / 2;
        if (A[mid] == target) return mid;
        if (left == right) return -1;
        if (left == right - 1) return A[right] == target ? right : -1;
        if (A[mid] > A[mid - 1]) {
            return searchin(A, left, mid - 1, target) >= searchin(A, mid, right, target)
                    ? searchin(A, left, mid - 1, target) : searchin(A, mid, right, target);
        }
        else {
            if (target > A[right]) return searchin(A, left, mid - 1, target);
            else return searchin(A, mid, right, target);
        }
    }