(sortedrotated.*)

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

Dữ liệu vào:

• Dòng đầu ghi số lượng testcase \(T\ (1 \leq T \leq 100)\). Mỗi testcase gồm:

  • Số nguyên \(n\ (1 \leq n \leq \ 10^{7})\)

  • 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}|\ \leq \ 10^{8},\ 0 \leq i \leq n)\)

  • Dòng thứ 3 ghi số nguyên \(x\ (1 \leq x \leq 10^{8})\)

  • 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 (\(a_{i}\
    eq \ a_{j}\) với \(\forall i\
    eq \ j\))

Kết quả: 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\).

Ví dụ: