Subarrays with a bounded maximum

Problem

A selector looks at a batter's scores from n innings, in order. A stretch is one or more innings next to each other.

Count the stretches whose highest score is at least L and at most R.

Input: The first line has three integers n, L and R. The second line has n integers: the scores, in order.
Output: One integer: the number of stretches.
Constraints: 1 ≤ n ≤ 10^5
0 ≤ L ≤ R ≤ 10^9
0 ≤ score ≤ 10^9

Example 1

Input

4 2 3
2 1 4 3

Output

The stretches [2], [2, 1] and [3] have a highest score from 2 to 3.

Example 2

Input

3 50 100
10 20 30

Output

Every score is below 50.

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

Hint 1

Checking every stretch and its highest score is O(n²). Try counting stretches with a simpler rule and combine the counts.

Hint 2

Count the stretches whose highest score is at most R. A run of t innings that are all ≤ R contains t × (t + 1) / 2 such stretches.

Hint 3

The stretches with highest score from L to R are those with highest ≤ R, minus those with highest ≤ L − 1.

Hint 4

Use one pass for each count and keep a running run length. With n = 10^5 the count can reach about 5 × 10^9, so use long.

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