問題文

$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 を出力せよ．

入力例 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 型になるように並べ替えることは不可能です．