9613: ABC247 —— E - Max Min
[Creator : ]
Description
We have a number sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and integers $X$ and $Y$. Find the number of pairs of integers $(L, R)$ satisfying all the conditions below.
- $1 \leq L \leq R \leq N$
- The maximum value of $A_L, A_{L+1}, \dots, A_R$ is $X$, and the minimum is $Y$.
- $1 \leq L \leq R \leq N$
- The maximum value of $A_L, A_{L+1}, \dots, A_R$ is $X$, and the minimum is $Y$.
Input
Input is given from Standard Input in the following format:
```
$N$ $X$ $Y$
$A_1$ $A_2$ $\dots$ $A_N$
```
```
$N$ $X$ $Y$
$A_1$ $A_2$ $\dots$ $A_N$
```
Output
Print the answer.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq Y \leq X \leq 2 \times 10^5$
- All values in input are integers.
- $1 \leq A_i \leq 2 \times 10^5$
- $1 \leq Y \leq X \leq 2 \times 10^5$
- All values in input are integers.
Sample 1 Input
4 3 1
1 2 3 1
Sample 1 Output
4
4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).
Sample 2 Input
5 2 1
1 3 2 4 1
Sample 2 Output
0
No pair (L,R) satisfies the condition.
Sample 3 Input
5 1 1
1 1 1 1 1
Sample 3 Output
15
It may hold that X=Y.
10 8 1
2 7 1 8 2 8 1 8 2 8
36