Trong kho dữ liệu của thư viện trường có một danh sách gồm n số nguyên dương được sắp xếp giảm dần theo mức độ ưu tiên. Thủ thư muốn nhanh chóng kiểm tra xem một mã số ưu tiên bất kỳ có nằm trong danh sách hay không. Nếu tìm tuần tự thì sẽ tốn rất nhiều thời gian do danh sách rất dài.

Vì vậy, thủ thư đề nghị bạn viết một chương trình hỗ trợ tìm kiếm nhanh bằng tìm kiếm nhị phân trên mảng giảm dần.

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, 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 giảm 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 x không có trong danh sách.