问题描述

设 $N$ 是一个正奇数。长度为 $N$ 的整数序列 $S = (S_1, S_2, \dots, S_N)$ 被称为M-型的，如果“对于每个偶数 $i = 2, 4, \dots, N - 1$，满足 $S_{i-1} < S_i$ 和 $S_i > S_{i+1}$”。

给定长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$。确定是否可以重新排列 $A$ 使其成为 M-型。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $N$ 是一个正奇数。
• $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$

输入

输入以以下格式从标准输入给出：

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

输出

如果可以重新排列给定的整数序列 $A$ 成为 M-型，则输出 Yes；否则输出 No。

示例输入 1

5
1 2 3 4 5

示例输出 1

Yes

给定的序列为 $A = (1, 2, 3, 4, 5)$。将其重新排列，例如为 $B = (4, 5, 1, 3, 2)$，

• 对于 $i = 2$，满足 $B_1 = 4 < 5 = B_2$ 和 $B_2 = 5 > 1 = B_3$；
• 对于 $i = 4$，满足 $B_3 = 1 < 3 = B_4$ 和 $B_4 = 3 > 2 = B_5$。

因此，序列 $B$ 是 M-型的，答案是 Yes。

示例输入 2

5
1 6 1 6 1

示例输出 2

Yes

给定的序列 $A$ 本身就是 M-型的。

示例输入 3

5
1 6 6 6 1

示例输出 3

No

无法将其重新排列为 M-型。