Tìm một phần tử x trong dãy đã được sắp xếp và quay vòng.

Một dãy được sắp xếp và quay vòng có dạng: nửa dãy đầu có giá trị tăng dần, rồi dãy tiếp theo cũng tăng dần. Dãy này có được từ dãy tăng dần dịch trái k vị trí.

Ví dụ: A = {3,4,5,1,2}; {4, 5, 1, 2, 3} là một dãy quay vòng đã được sắp xếp. Cần tìm một phần tử có giá trị x trong dãy với độ phức tạp O(logn) bằng áp dụng thuật toán tìm kiếm nhị phân.

Input:

• Dòng đầu ghi số lượng testcase T (1 ≤ T ≤ 100). Mỗi testcase gồm:
  • Số nguyên N (1 ≤ N ≤ 10⁷).
  • Dòng thứ hai ghi N số nguyên cách nhau bởi dấu cách, các phần tử được đánh chỉ số từ 0 (|a_i| ≤ 10⁸, 0 ≤ i ≤ N).
  • Dòng thứ 3 ghi số nguyên x (1 ≤ x ≤ 10⁸).
  • Dữ liệu đảm bảo dãy đã cho là dãy được sắp xếp vòng, các phần tử trong dãy khác nhau đôi một (ai ≠ aj với ∀i ≠ j).

Output: Với mỗi test, ghi một số nguyên là vị trí phần tử x trong dãy, nếu không tồn tại phần tử x, hãy in ra -1.