Description

对于一个长度为 $(2 \cdot k + 1)$ 的数组，我们将其元素按非递减顺序排序后，第 $(k + 1)$ 位的数字称为该数组的中位数。例如，数组 $[1]$、$[4,2,5]$ 和 $[6,5,1,2,3]$ 的中位数分别是 $1$、$4$ 和 $3$。

给定一个长度为偶数 $n$ 的整数数组 $a$。

判断是否可以将 $a$ 分割成若干个长度为奇数的子数组，使得所有这些子数组的中位数都相等。

形式化地说，你需要判断是否存在一个整数序列 $i_1, i_2, \ldots, i_k$，满足以下条件：

• $1 = i_1 < i_2 < \ldots < i_k = (n + 1)$；
• $(i_2 - i_1) \bmod 2 = (i_3 - i_2) \bmod 2 = \ldots = (i_k - i_{k - 1}) \bmod 2 = 1$；
• $f(a[i_1..(i_2-1)]) = f(a[i_2..(i_3-1)]) = \ldots = f(a[i_{k - 1}..(i_k - 1)])$，其中 $a[l..r]$ 表示由元素 $a_l, a_{l + 1}, \ldots, a_r$ 组成的子数组，$f(a)$ 表示数组 $a$ 的中位数。

Input Format

第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）——数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。

保证 $n$ 是偶数。

Output Format

如果可以将 $a$ 分割成若干个长度为奇数的子数组，且这些子数组的中位数都相等，则输出 Yes，否则输出 No。

4
1 1 1 1

Yes

6
1 2 3 3 2 1

Yes

6
1 2 1 3 2 3

No

Hint

在第一个样例中，数组 $[1,1,1,1]$ 可以分割为 $[1]$ 和 $[1,1,1]$，它们的中位数均为 $1$。

在第二个样例中，数组 $[1,2,3,3,2,1]$ 可以分割为 $[1,2,3]$ 和 $[3,2,1]$，它们的中位数均为 $2$。

在第三个样例中，数组 $[1,2,1,3,2,3]$ 无法被分割为若干个长度为奇数的子数组，且这些子数组的中位数相等。

评分标准

• （$3$ 分）：$n=2$；
• （$14$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 2$；
• （$12$ 分）：对于 $1 \le i < n$，$a_i \le a_{i+1}$；
• （$16$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 3$，且每个值在 $a$ 中出现的次数不超过 $\frac{n}{2}$；
• （$17$ 分）：$n \le 100$；
• （$18$ 分）：$n \le 2000$；
• （$20$ 分）：无额外限制。

翻译由 DeepSeek V3 完成