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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class Solution {
//    ----------------------------------------------------------------------------

    static class Task {
        
        public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
            
            int n = in.nextInt();
            int a[] = in.nextIntArray(n);
            if (n == 1) {
                out.print("YES");
                return;
            }
            //count of any one number cannot exceed (n+1)/2
            int count[] = new int[1001];
            int cannotExceed = (n + 1) / 2;
            for (int i = 0; i < n; i++) {
                count[a[i]]++;
                if (count[a[i]] > cannotExceed) {
                    
                    out.print("NO");
                    return;
                }
                
            }
            
            out.print("YES");
            
        }
    }
//    ----------------------------------------------------------------------------
    // IMPORTANT || COMMON  METHODS
    // PAIR

    static boolean[] sieveOfEratosthenes(int n) {
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            prime[i] = true;
        }
        
        prime[0] = false;
        prime[1] = false;
        
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }

//        returns the boolean array
        return prime;
    }
    
    static class Pair {
        
        int x;
        int y;

        // Constructor 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        // how to initialize
//            Pair level[] = new Pair[n];
//            for (int i = 0; i < n; i++) {
//                int x = in.nextInt();
//                int y = in.nextInt();
//
//                level[i] = new Pair(x, y);
//
//            }
        // How to sort
//              PairSort ps = new PairSort();
//              ps.sort(level, 1);
    }
    
    static class PairSort {
        
        Pair[] sort(Pair arr[], int i) {
            // Comparator to sort the pair according to second element 
            Arrays.sort(arr, new Comparator<Pair>() {
                @Override
                public int compare(Pair p1, Pair p2) {
                    // 1 sees the first elements ans sorts them in increasing order 
                    // 2 sees the second elements ans sorts them in increasing order 
                    // 3 sees the first elements ans sorts them in decreasing order 
                    // 4 sees the second elements ans sorts them in decreasing order 
                    switch (i) {
                        case 2:
                            return p1.y - p2.y;
                        case 1:
                            return p1.x - p2.x;
                        case 4:
                            return p2.y - p1.y;
                        default:
                            return p2.x - p1.x;
                    }
                    
                }
            });
            
            return arr;
        }
    }

    // GCD || HCF
    static long GCD(long x, long y) {
        return y == 0 ? x : GCD(y, x % y);
    }

    // LCM 
    static long LCM(long a, long b) {
        return (a * b) / GCD(a, b);
    }

    // Returns the divisors of a number
    static ArrayList Divisors(long n) {
        ArrayList<Long> div = new ArrayList<>();
        
        for (long i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                div.add(i);
                
                if (n / i != i) {
                    div.add(n / i);
                }
            }
        }
        return div;
    }

    // PERMUTATIONS
    static void permute(int[] a, int k) {
        if (k == a.length) {
            
            for (int i = 0; i < k; i++) {
                
                System.out.print(a[i] + " ");
                
            }
            
            System.out.println("");
        } else {
            for (int i = k; i < a.length; i++) {
                int temp = a[k];
                a[k] = a[i];
                a[i] = temp;
                
                permute(a, k + 1);
                // swapping a[k] and a[i] .
                temp = a[k];
                a[k] = a[i];
                a[i] = temp;
            }
        }

        // How to run 
        //int seq[] = {1, 19, 6}; .. let seq be the array of numbers to be permuted
        //permute(seq, 0); // call this function . 
        //0 -> all permutations ( permutation start from 1st number) 
        //1-> permutations start from 2nd number 
        //2-> permutation start from 3rd number
        // n-1 that array will be returned
    }
//    ----------------------------------------------------------------------------
    // MAIN - INPUT - OUTPUT 

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
    
    static class InputReader {
        
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public Double nextDouble() {
            return Double.parseDouble(next());
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
            
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
            
            return array;
        }
        
    }
}

// to take the string as a single character each . do this.

/*          BufferedReader inn = new BufferedReader(new InputStreamReader(System.in));
            char[] s1 = inn.readLine().toCharArray();
            // for going through each ch in ch array
            for (char c : s1) {
                if (c != ' ') {

                }

            }
 */
