Max Min Subarrays :
Difficulty Level : Medium
Submissions : 505
Asked In :
Marks :15
: 20 | : 0
We have a number sequence $$$A=[A_1,A_2,…,A_N]$$$ of length $$$N$$$ and integers $$$X$$$ and $$$Y$$$. Find the number of pairs of integers $$$(L,R)$$$ satisfying all the following conditions :
- $$$1 \le L \le R \le N$$$
- The maximum value of $$$A_L,A_{L+1},…,A_R$$$ is $$$X$$$, and the minimum is $$$Y$$$.
The first line of input contains three space separated integers $$$N \hspace{2pt} (1 \le N \le 2 \times 10^5)$$$, $$$X$$$ and $$$Y$$$ $$$(1 \le Y \le X \le 2 \times 10^5)$$$ — the number of elements in the array $$$A$$$ and the values $$$X$$$ and $$$Y$$$ specified in the problem statement.
The second line of input contains $$$n$$$ space separated integers $$$A_1, A_2, ... A_N$$$ $$$(1 \le A_i \le 2 \times 10^5)$$$ — the elements of array $$$A$$$.
Print a single integer — the answer to the problem in a single line.
4 3 1 1 2 3 1
4
5 2 1 1 3 2 4 1
0
5 1 1 1 1 1 1 1
15
10 8 1 2 7 1 8 2 8 1 8 2 8
36
In sample test case 1, $$$4$$$ pairs satisfy the conditions: $$$(L,R)=(1,3),(1,4),(2,4),(3,4)$$$.
In sample test case 2, No pair $$$(L,R)$$$ satisfies the condition.
