Yaroslav has an array that consists of n integers. In one second Yaroslav can swap two neighboring array elements. Now Yaroslav is wondering if he can obtain an array where any two neighboring elements would be distinct in a finite time.

Help Yaroslav.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000) — the array elements.

Output

In the single line print "YES" (without the quotes) if Yaroslav can obtain the array he needs, and "NO" (without the quotes) otherwise.

Examples

Input

1
1


Output

YES


Input

3
1 1 2


Output

YES


Input

4
7 7 7 7


Output

NO

Note

In the first sample the initial array fits well.

In the second sample Yaroslav can get array: 1, 2, 1. He can swap the last and the second last elements to obtain it.

In the third sample Yarosav can't get the array he needs.
#!/usr/bin/env python
# coding: utf-8

# In[204]:


# # n = int(input())
# # line = list(map(int, input().split()))
# # line = list(str(input()))


# In[1]:


from collections import Counter


# In[ ]:


# 56
# 516 76 516 197 516 427 174 516 706 813 94 37 516 815 516 516 937 483 16 516 842 516 638 691 516 635 516 516 453 263 516 516 635 257 125 214 29 81 516 51 362 516 677 516 903 516 949 654 221 924 516 879 516 516 972 516
# 100
# 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
# 46
# 314 723 314 314 314 235 314 314 314 314 270 314 59 972 314 216 816 40 314 314 314 314 314 314 314 381 314 314 314 314 314 314 314 789 314 957 114 942 314 314 29 314 314 72 314 314


# In[33]:


n = int(input())
line = list(map(int, input().split()))


# In[36]:


if len(line) == 1:
    print("YES")
else:
    count_dict = Counter(line)
    seg_val = []
    seg_tmp = []
    seg_len = 0
    n_seg = 0
    
    max_count = max(count_dict.values())
    max_key = []
    accum = 0
    for k, v in count_dict.items():
        if v != max_count:
            accum += count_dict[k]
        else:
            max_key.append(k)
    max_key = set(max_key)

    for i in range(n):
        if i == 0 or line[i] == line[i-1]:
            seg_tmp.append(line[i])

        if len(seg_tmp) > 1 and (line[i] != line[i-1] or i == n-1):
            seg_len = max(seg_len, len(seg_tmp))
            n_seg += 1
            seg_val.append(seg_tmp[0])
            seg_tmp = []
    seg_val = set(seg_val)
    
    max_len = n//2 if n%2 == 0 else (n//2 + 1)
    
    if (seg_len > max_len) or (accum < max_count - 1 and len(max_key) < 2):
        print("NO")
    else:
        print("YES")


# In[ ]:




