Where does a new price go

Problem

Prices are kept in ascending order and may repeat. A new price arrives. Print the position where it must be inserted so the list stays sorted, placing it before any equal prices.

Input, output and limits

Input: Line 1: n. Line 2: n prices in ascending order. Line 3: the new price p.
Output: One integer from 0 to n.
Constraints: 1 ≤ n ≤ 10^5
1 ≤ price, p ≤ 10^9

Examples

Example 1

Input

5
10 20 20 30 40
20

Output

Example 2

Input

5
10 20 20 30 40
25

Output

Hints

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

Hint 1

The answer is the first position whose price is not smaller than p.

Hint 2

The bisect module has a function for exactly this position.

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

Solve in the editor

Find an order ideasy
Count one stock leveleasy
Integer square rooteasy
First and last position of a leveleasy
Smallest bundle that is large enougheasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems

Problem

Input, output and limits

Examples

Hints

More Binary Search problems