Binary Search

You are given N distinct integers in increasing order, and a value X. Print the position of X in the list using 0-based indexing, or -1 if X is not present.

For the list 1 3 5 7 9, the value 7 sits at index 3.

The list can be very large, so a plain left-to-right scan is not the intended solution — halve the search range each step instead.

💡

Keep two bounds, low and high. Look at the middle element: if it is too small, move low past it; if too large, move high before it. Stop when the bounds cross.

Input

Line 1: the integer N. Line 2: N distinct integers in increasing order. Line 3: the integer X.

Output

A single integer: the 0-based index of X, or -1 if it is absent.

Constraints

1 <= N <= 10^5, values between -10^9 and 10^9, sorted strictly increasing

Example 1

Input

5
1 3 5 7 9
7

Output

Counting from 0, the value 7 is the fourth element, at index 3.

Submit runs your code against 6 test cases — the 1 shown above plus 5 hidden ones covering the awkward cases. Run sample just tries the first example, which is usually what you want while you are still working it out.