Cho mảng số nguyên ~a_0,a_1,…,a_{n-1}~ được sắp xếp theo thứ tự tăng dần (với các giá trị khác nhau). Mảng a có thể bị xoay tại một vị trí không xác định k (0<k<n) sao cho mảng kết quả là ~a_k,a_{k+1},…,a_{n-1},a_0,a_1,…,a_{k-1}~. Ví dụ, [0,1,2,4,5,6,7] có thể bị xoay tại vị trí 3 và trở thành [4,5,6,7,0,1,2].</p>

Cho mảng a sau khi xoay và một số nguyên t, trả về chỉ số của t nếu nó xuất hiện trong a, hoặc -1 nếu nó không nằm trong a.

Yêu cầu:

Thuật toán tìm kiếm phải có độ phức tạp O(log n).

Dữ liệu:

Dòng 1: Chứa mảng số nguyên ~a_0,a_1,…,a_{n-1}~.
Dòng 2: Chứa số nguyên t cần tìm.

Kết quả:

Một dòng duy nhất là kết quả tìm được.

Giới hạn:

• ~1≤n≤10^5.~
  
• ~-10^9≤a_i≤10^9.~

Input 1

4 5 6 7 0 1 2
0

Output 1

4

Input 2

4 5 6 7 0 1 2
3

Output 2

-1