Cho một mảng \(A\) có \(n\) số nguyên \((a_1,a_2...a_n)\) và một số nguyên \(t\). Hãy viết chương trình tìm kiếm vị trí \(t\) trong mảng số nguyên \(A\), nếu không tìm được thì in \(-1\)

Lưu ý: Mảng đã được sắp xếp tăng dần, vị trí bắt đầu tính từ 0.

Yêu cầu: thuật toán phải chạy với độ phức tạp \(O(log_n)\)

Dữ liệu vào:

• Dòng thứ nhất: chứa hai số \(n\) và \(t\)
• Dòng thứ hai: chứa \(n\) số nguyên

Ràng buộc:

• \(1 \le n \le 10^7\)
• \(-10^7 \lt a_i, t \lt 10^7\)
• Tất cả số nguyên \(a_i\) là duy nhất

Input

6 9
-1 0 3 5 9 12

Output

4

Input

6 2
-1 0 3 5 9 12

Output

-1