配点 : $300$ 点

問題文

$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 \ \ (1 \leq i \leq N)$

入力

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

$N$

$A_1 \ A_2 \ \dots \ A_N$

出力

与えられた整数列 $A$ を M 型になるように並べ替えることが可能なら Yes を，不可能なら No を出力せよ．

5
1 2 3 4 5

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 です．

5
1 6 1 6 1

Yes

与えられた数列 $A$ 自身が M 型です．

5
1 6 6 6 1

No

M 型になるように並べ替えることは不可能です．