[AdditionalFile5222.zip](file://AdditionalFile5222.zip?type=additional_file)

#5222. 「UOI 2023 Stage 4 Day2」数组与子数组中位数

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day2 T1. Масив і медіани підмасивів

我们定义长度为 $(2 \cdot k + 1)$ 的数组的中位数为在数组按非降序排序后位于第 $(k + 1)$ 位的数字。例如，数组 $[1]$、$[4, 2, 5]$ 和 $[6, 5, 1, 2, 3]$ 的中位数分别是 $1$、$4$ 和 $3$。

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

你需要判断是否可以将数组 $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$ 的中位数。

输入格式

输入的第一行包含一个偶数 $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$ 为偶数。

输出格式

如果可以将数组 $a$ 划分为若干个奇数长度的子数组，使得这些子数组的中位数两两相等，则输出 Yes；否则输出 No。

样例 1

输入

4
1 1 1 1

输出

Yes

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

样例 2

输入

6
1 2 3 3 2 1

输出

Yes

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

样例 3

输入

6
1 2 1 3 2 3

输出

No

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

数据范围与提示

详细子任务附加限制及分值如下表所示：