Subarrays with Bounded Maximum

Difficulty: 1700 5000 ms 128 MB

two-pointers

Count the contiguous subarrays whose maximum element lies in [LO, HI].

Input: the first line has N, LO and HI; the second line has N integers.

Output: the number of subarrays with LO ≤ max ≤ HI.

Constraints:

• 1 ≤ N ≤ 10⁵
• |values| ≤ 10⁶
• |LO|, |HI| ≤ 10⁶

Sample Tests

5 2 4
1 3 5 2 4

5

3 1 1
1 1 1

6

Read the Editorial