Trên bàn giáo viên có một danh sách gồm n số nguyên dương đã được sắp xếp tăng dần. Do danh sách quá dài nên việc tìm một số bất kỳ trong đó bằng cách dò tuần tự sẽ mất rất nhiều thời gian.

Thầy giáo muốn bạn viết một chương trình để hỗ trợ việc tìm kiếm nhanh hơn bằng phương pháp tìm kiếm nhị phân (Binary Search).

Yêu cầu

Cho một số nguyên dương x. Hãy xác định vị trí xuất hiện của x trong dãy (tính theo chỉ số từ 1).

• Nếu x xuất hiện trong dãy, hãy in ra vị trí của nó.

• Nếu x không xuất hiện trong dãy, in ra -1.

Dữ liệu vào

• Dòng 1: Số nguyên n (1 ≤ n ≤ 10⁶).

• Dòng 2: n số nguyên dương đã được sắp xếp tăng dần.

• Dòng 3: Số nguyên cần tìm x.

Dữ liệu ra

• Một số nguyên duy nhất — vị trí của x trong dãy hoặc -1 nếu không có.

Ví dụ