410276: GYM103999 E CntSeq

RMN wasted all his money on sports betting...again. However, he still feels the need of betting just one more time in order to at least recover his losses.

The only issue is that he needs a big sum to get a good return on his last "safe" bet. Because he doesn't have a lot of skills, he can't get this money too easily. Luckily, a man in the parking spot of a gas station offered him 100 RON if he can count how many substrings of an integer sequence have their maximum value between two given values.

More formally, RMN receives an integer sequence $$$A$$$ of $$$N$$$ numbers, and two integers $$$L$$$ and $$$U$$$. He is asked to count how many substrings $$$S = A[i,i+1\cdots j]$$$ have $$$L \leq max(S) \leq U$$$.

Help RMN retire in glory by winning the 100 RON needed for his first win!

P.S. He will probably lose anyway :(

The first line will contain 3 integers $$$N$$$ ($$$ 1 \leq N \leq 10^5$$$), $$$L$$$ ($$$-10^{18} \leq L \leq 10^{18}$$$), $$$U$$$ ($$$-10^{18} \leq U \leq 10^{18}$$$) - the length of the array $$$A$$$, the lower and the upper bounds for the maximum of the substrings that need to be counted. The following line will contain $$$N$$$ integers between $$$-10^{18}$$$ and $$$10^{18}$$$ - the values of the sequence $$$A$$$.

The only line will contain a single integer - the number of substrings of $$$A$$$ with their maximum value between $$$L$$$ and $$$U$$$.

• for 25 points, it is guaranteed that $$$N \leq 500$$$
• for another 25 points, it is guaranteed that $$$N \leq 5000$$$
• for the last 50 points, we have $$$N \leq 10^5$$$

5 3 4
1 5 2 4 3

5

The substrings with their maximum value between 3 and 4 are: $$$[4], [2,4], [4,3], [4,3,2], [3]$$$