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 无法获得他需要的数组。