题目描述
N を正の奇数とします. 長さ N の整数列 S = (S1, S2, …, SN) が M 型であるとは,「各偶数 i = 2, 4, …, N − 1 について Si−1 < Si かつ Si > Si+1 が成り立つ」ことを言います.
長さ N の正整数列 A = (A1, A2, …, AN) が与えられます. A を M 型になるように並べ替えることが可能かどうかを判定してください.
输入格式
入力は以下の形式で標準入力から与えられる.
N A1 A2 … AN
输出格式
与えられた整数列 A を M 型になるように並べ替えることが可能なら Yes
を,不可能なら No
を出力せよ.
题目大意
题目描述
N 是一个正奇数。我们称一个长度为 N 的序列 S 是 M 型序列,当前仅当对于所有的 i=2,4,6,…,N−1(即偶数位),都有 Si−1<Si 且 Si>Si+1。
现在给定你一个长度为 N 的序列 A,请你判断能否通过将 A 序列里的元素打乱位置使其变为一个 M 型序列。
输入格式
输入共两行
第一行一个整数 N,表示序列长度。
第二行共 N(1≤N≤2×105)个整数,第 i 个整数为 Ai(1≤Ai≤109)。
输出格式
共一行一个字符串,如果 A 序列能够通过被打乱元素顺序变成 M 型序列,输出 Yes
,否则输出 No
。
5
1 2 3 4 5
Yes
5
1 6 1 6 1
Yes
5
1 6 6 6 1
No
提示
制約
- 1 ≤ N ≤ 2 × 105
- N は奇数である.
- 1 ≤ Ai ≤ 109 (1 ≤ i ≤ N)
Sample Explanation 1
与えられた数列は A = (1, 2, 3, 4, 5) です. これを並べ替えて,たとえば B = (4, 5, 1, 3, 2) とすると, - i = 2 について B1 = 4 < 5 = B2 かつ B2 = 5 > 1 = B3 が成り立ち, - i = 4 について B3 = 1 < 3 = B4 かつ B4 = 3 > 2 = B5 が成り立ちます. したがって,この数列 B は M 型であり,答えは Yes
です.
Sample Explanation 2
与えられた数列 A 自身が M 型です.
Sample Explanation 3
M 型になるように並べ替えることは不可能です.