Find the delivery slot

Problem

Delivery slots are sorted from earliest to latest and are all different. Report the position (from 0) of a requested slot, or -1 if it is not in the list.

Input, output and limits

Input: Line 1: n. Line 2: n sorted integers. Line 3: the requested slot.
Output: One integer.
Constraints: 1 ≤ n ≤ 10^5
The slots are strictly increasing
-10^9 ≤ slot ≤ 10^9

Examples

Example 1

Input

5
10 20 30 40 50
40

Output

At position 3.

Example 2

Input

5
10 20 30 40 50
35

Output

-1

Hints

Try the problem first. Open one hint at a time.

Hint 1

The list is sorted, so look at the middle and throw away half each time.

Hint 2

Keep two ends, lo and hi, and stop when lo passes hi.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

First ticket seen twiceeasy
The odd one outeasy
Sales between two dayseasy
Whole blocks onlyeasy
Reads the same both wayseasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Pattern Practice problems

Problem

Input, output and limits

Examples

Hints

More Pattern Practice problems