A product catalog keeps its prices in a single list sorted in non-decreasing order. You want to insert one more price x while keeping the list sorted. Print the leftmost 0-indexed position at which x can be placed so that the list stays sorted in non-decreasing order.
Equivalently, this is the number of prices that are strictly less than x. If x is not larger than any existing price, the answer is 0; if x is larger than every price, the answer is n.
Input format
Line 1: an integer n, the number of prices.
Line 2: n space-separated integers in non-decreasing order.
Line 3: an integer x, the price to insert.
Output format
A single integer: the leftmost insertion index (0-indexed).
Constraints
- 1 <= n <= 100000
- -1000000000 <= each price, x <= 1000000000
- The prices are given in non-decreasing order.