102474: [AtCoder]ABC247 E - Max Min

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

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$.

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.

Input

Input is given from Standard Input in the following format:

$N$ $X$ $Y$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer.


Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

$4$ pairs satisfy the conditions: $(L,R)=(1,3),(1,4),(2,4),(3,4)$.


Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair $(L,R)$ satisfies the condition.


Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that $X=Y$.


Sample Input 4

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

Sample Output 4

36

Input

题意翻译

给定数列 $ A_n $,给定 $ X, Y $,我们定义数对 $ (L, R) $ 满足 $ 1 \le L \le R \le n $,且数列 $ A_L, A_{L + 1}, \cdots, A_R $ 满足最大值为 $ X $,最小值为 $ Y $,求有多少种满足条件的数对。

Output

分数: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$

输出

打印答案。


样例输入 1

4 3 1
1 2 3 1

样例输出 1

4

有 $4$ 对满足条件的 $(L,R)$:$(L,R)=(1,3),(1,4),(2,4),(3,4)$。


样例输入 2

5 2 1
1 3 2 4 1

样例输出 2

0

没有满足条件的 $(L,R)$ 对。


样例输入 3

5 1 1
1 1 1 1 1

样例输出 3

15

可能满足 $X=Y$。


样例输入 4

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

样例输出 4

36

加入题单

上一题 下一题 算法标签: