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.
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.
A single integer: the leftmost insertion index (0-indexed).
Example 1
Input
5 2 4 4 6 9 5
Expected
3
Explanation
The prices strictly less than 5 are 2, 4 and 4 (three of them), so 5 belongs at index 3.
Example 2
Input
4 10 20 30 40 10
Expected
0
Explanation
No price is strictly less than 10, so 10 is inserted at the front, index 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →