You are given an array of integers sorted in non-decreasing order and an inclusive query range [lo, hi] with lo <= hi. Count how many array values v satisfy lo <= v <= hi. Duplicate values each count separately.
The intended solution locates the lower bound of lo and the upper bound of hi with two binary searches and returns the difference of their positions, giving an O(log n) query.
Input format
Line 1: an integer n, the length of the array.
Line 2: n space-separated integers in non-decreasing order (this line is empty when n = 0).
Line 3: two space-separated integers lo and hi with lo <= hi.
Output format
A single integer: the count of array values inside the inclusive range [lo, hi].
Constraints
- 0 ≤ n ≤ 100000
- -1000000000 ≤ each array value ≤ 1000000000
- -1000000000 ≤ lo ≤ hi ≤ 1000000000
- The array is guaranteed to be sorted in non-decreasing order.