275. How Many Fall in the Range

Core1000 ms256 MBSolved by 0%

Given n integers and two bounds lo and hi, print how many values satisfy lo <= value <= hi. Both bounds are inclusive.

Counting by scanning is O(n) and perfectly fine for one question. Sorting first costs O(n log n) once and then answers this in O(log n), which is the arrangement you want when many ranges are asked about the same data.

Both endpoints are lower bounds, which is why that one search keeps earning its place.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ lo ≤ hi ≤ 1000000000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains three integers n, lo and hi. The second line contains n integers.

Output

Print one integer, the count of values within the inclusive range.

Input5 2 4 1 2 3 4 5

Output3

Notehas a range covering three of five values

Input3 5 10 1 2 3

Output0

Notehas a range entirely above the data

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution