← 返回题目列表

AtCoder · arc161_a

A. 使 M

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

让 N 积极 奇数 号码。 长度为整数的序列 N, S = (S_1, S_2, \dots, S_N),据说是 M型 if“对于每个偶数 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型。