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.
import java.io.*;
import java.util.*;

public class YaroslavPermutations_296A {
  public static void main(String[] args) throws IOException{
    FastReader fr = new FastReader();
    PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
    
    int n = fr.nextInt();
    PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> b.y - a.y);
    Map<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < n; i++) {
      int add = fr.nextInt();
      map.putIfAbsent(add, 0);
      map.put(add, map.get(add) + 1);
    }

    for (Map.Entry<Integer, Integer> a : map.entrySet()) {
      pq.add(new Pair(a.getKey(), a.getValue()));
    }

    while (pq.size() > 1) {
      Pair a = pq.poll();
      Pair b = pq.poll();

      a.y--;
      b.y--;

      if (a.y > 0) pq.add(a);
      if (b.y > 0) pq.add(b);
    }

    if (pq.size() == 1) {
      if (pq.poll().y > 1) {
        pr.println("NO");
        pr.close();
        return;
      }
    }

    pr.println("YES");
    pr.close();
  }

  static class Pair {
      int x, y;
      public Pair(int x, int y) {
          this.x = x;
          this.y = y;
      }
  }

  static int toInt(String s) {
    return Integer.parseInt(s);
  }

  static class FastReader 
  { 
      BufferedReader br; 
      StringTokenizer st; 

      public FastReader() throws FileNotFoundException 
      { 
          br = new BufferedReader(new InputStreamReader(System.in)); 
      } 

      String next() 
      { 
          while (st == null || !st.hasMoreElements()) 
          { 
              try
              { 
                  st = new StringTokenizer(br.readLine()); 
              } 
              catch (IOException  e) 
              { 
                  e.printStackTrace(); 
              } 
          } 
          return st.nextToken(); 
      } 

      int nextInt() 
      { 
          return Integer.parseInt(next()); 
      } 

      long nextLong() 
      { 
          return Long.parseLong(next()); 
      } 

      double nextDouble() 
      { 
          return Double.parseDouble(next()); 
      } 

      String nextLine() 
      { 
          String str = ""; 
          try
          { 
              str = br.readLine(); 
          } 
          catch (IOException e) 
          { 
              e.printStackTrace(); 
          } 
          return str; 
      } 
  }
}
