← 返回题目列表

Codeforces · 296/A

A. 雅罗斯拉夫和排列

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

Yaroslav 有一个由 n 个整数组成的数组。一秒钟内,雅罗斯拉夫可以交换两个相邻的数组元素。现在雅罗斯拉夫想知道他是否可以获得一个数组,其中任何两个相邻元素在有限时间内都是不同的。

帮助雅罗斯拉夫。

输入

第一行包含整数 n (1 ≤ n ≤ 100) — 数组中的元素数量。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1000) — 数组元素。

输出

如果 Yaroslav 可以获得他需要的数组,则在单行中打印“YES”(不带引号),否则打印“NO”(不带引号)。

示例

输入 #1

1
1

输出 #1

YES

输入 #2

3
1 1 2

输出 #2

YES

输入 #3

4
7 7 7 7

输出 #3

NO

注意

在第一个示例中,初始数组拟合得很好。

在第二个样本中,Yaroslav 可以得到数组:1,2,1。他可以交换最后一个和倒数第二个元素来获得它。

在第三个示例中,Yarosav 无法获得他需要的数组。