atcoder#ARC161A. [ARC161A] Make M

[ARC161A] Make M

题目描述

N N を正の奇数とします. 長さ N N の整数列 S = (S1, S2, , SN) S\ =\ (S_1,\ S_2,\ \dots,\ S_N) M 型であるとは,「各偶数 i = 2, 4, , N  1 i\ =\ 2,\ 4,\ \dots,\ N\ -\ 1 について Si1 < Si S_{i-1}\ <\ S_i かつ Si > Si+1 S_i\ >\ S_{i+1} が成り立つ」ことを言います.

長さ N N の正整数列 A = (A1, A2, , AN) A\ =\ (A_1,\ A_2,\ \dots,\ A_N) が与えられます. A A を M 型になるように並べ替えることが可能かどうかを判定してください.

输入格式

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

N N A1 A2  AN A_1\ A_2\ \dots\ A_N

输出格式

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

题目大意

题目描述

NN 是一个正奇数。我们称一个长度为 NN 的序列 SSM 型序列,当前仅当对于所有的 i=2,4,6,,N1i=2,4,6,\dots,N-1(即偶数位),都有 Si1<SiS_{i-1}<S_{i}Si>Si+1S_{i}>S_{i+1}

现在给定你一个长度为 NN 的序列 AA,请你判断能否通过将 AA 序列里的元素打乱位置使其变为一个 M 型序列。

输入格式

输入共两行

第一行一个整数 NN,表示序列长度。

第二行共 N(1N2×105)N(1\le N\le2\times10^5)个整数,第 ii 个整数为 Ai(1Ai109)A_{i}(1\le A_{i}\le10^9)

输出格式

共一行一个字符串,如果 AA 序列能够通过被打乱元素顺序变成 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 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • N N 奇数である.
  • 1  Ai  109 (1  i  N) 1\ \leq\ A_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N)

Sample Explanation 1

与えられた数列は A = (1, 2, 3, 4, 5) A\ =\ (1,\ 2,\ 3,\ 4,\ 5) です. これを並べ替えて,たとえば B = (4, 5, 1, 3, 2) B\ =\ (4,\ 5,\ 1,\ 3,\ 2) とすると, - i = 2 i\ =\ 2 について B1 = 4 < 5 = B2 B_1\ =\ 4\ <\ 5\ =\ B_2 かつ B2 = 5 > 1 = B3 B_2\ =\ 5\ >\ 1\ =\ B_3 が成り立ち, - i = 4 i\ =\ 4 について B3 = 1 < 3 = B4 B_3\ =\ 1\ <\ 3\ =\ B_4 かつ B4 = 3 > 2 = B5 B_4\ =\ 3\ >\ 2\ =\ B_5 が成り立ちます. したがって,この数列 B B は M 型であり,答えは Yes です.

Sample Explanation 2

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

Sample Explanation 3

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