配点 : $500$ 点

問題文

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ および整数 $X, Y$ があります。 次の条件をすべて満たす整数の組 $(L, R)$ の個数を求めてください。

• $1 \leq L \leq R \leq N$
• $A_L, A_{L+1}, \dots, A_R$ の最大値は $X$ であり、最小値は $Y$ である。

制約

• $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$
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $Y$

$A_1$ $A_2$ $\dots$ $A_N$

出力

答えを出力せよ。

4 3 1
1 2 3 1

4

条件を満たすのは $(L,R)=(1,3),(1,4),(2,4),(3,4)$ の $4$ 通りです。

5 2 1
1 3 2 4 1

0

条件を満たす $(L,R)$ は存在しません。

5 1 1
1 1 1 1 1

15

$X=Y$ である場合もあります。

10 8 1
2 7 1 8 2 8 1 8 2 8

36