Bear Limak has n colored balls, arranged in one long row. Balls are numbered 1 through n, from left to right. There are n possible colors, also numbered 1 through n. The i-th ball has color ti.

For a fixed interval (set of consecutive elements) of balls we can define a dominant color. It's a color occurring the biggest number of times in the interval. In case of a tie between some colors, the one with the smallest number (index) is chosen as dominant.

There are <image> non-empty intervals in total. For each color, your task is to count the number of intervals in which this color is dominant.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of balls.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ n) where ti is the color of the i-th ball.

Output

Print n integers. The i-th of them should be equal to the number of intervals where i is a dominant color.

Examples

Input

4
1 2 1 2


Output

7 3 0 0 


Input

3
1 1 1


Output

6 0 0 

Note

In the first sample, color 2 is dominant in three intervals:

  * An interval [2, 2] contains one ball. This ball's color is 2 so it's clearly a dominant color. 
  * An interval [4, 4] contains one ball, with color 2 again. 
  * An interval [2, 4] contains two balls of color 2 and one ball of color 1. 



There are 7 more intervals and color 1 is dominant in all of them.
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Colors {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt()-1;
        }
        int[] dom = new int[n];
        for (int i = 0; i < n; i++) {
            IndexMaxPQ<Integer> pq = new IndexMaxPQ<Integer>(n);
            for (int j = i; j < n; j++) {
                if(!pq.contains(a[j])){
                    pq.insert(a[j], n-a[j]);
                }
                pq.increaseKey(a[j], pq.keyOf(a[j]) + n);
                int best = pq.maxIndex();
                dom[best]++;
            }
        }
        for(int i=0;i<n;i++){
            System.out.print(dom[i] + " ");
        }
    }
    static class Node implements Comparable<Node>{
        int color;
        int idx;
        public Node(int color, int idx) {
            super();
            this.color = color;
            this.idx = idx;
        }
        @Override
        public int compareTo(Node o) {
            if(this.color - o.color != 0)
                return this.color - o.color;
            return this.idx - o.idx;
        }
        
    }
    
    public static class IndexMaxPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
        private int N;           // number of elements on PQ
        private int[] pq;        // binary heap using 1-based indexing
        private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
        private Key[] keys;      // keys[i] = priority of i

        /**
         * Initializes an empty indexed priority queue with indices between <tt>0</tt>
         * and <tt>maxN - 1</tt>.
         *
         * @param  maxN the keys on this priority queue are index from <tt>0</tt> to <tt>maxN - 1</tt>
         * @throws IllegalArgumentException if maxN < 0
         */
        public IndexMaxPQ(int maxN) {
            keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
            pq   = new int[maxN + 1];
            qp   = new int[maxN + 1];                   // make this of length maxN??
            for (int i = 0; i <= maxN; i++)
                qp[i] = -1;
        }

        /**
         * Returns true if this priority queue is empty.
         *
         * @return <tt>true</tt> if this priority queue is empty;
         *         <tt>false</tt> otherwise
         */
        public boolean isEmpty() {
            return N == 0;
        }

        /**
         * Is <tt>i</tt> an index on this priority queue?
         *
         * @param  i an index
         * @return <tt>true</tt> if <tt>i</tt> is an index on this priority queue;
         *         <tt>false</tt> otherwise
         * @throws IndexOutOfBoundsException unless (0 &le; i < maxN)
         */
        public boolean contains(int i) {
            return qp[i] != -1;
        }

        /**
         * Returns the number of keys on this priority queue.
         *
         * @return the number of keys on this priority queue 
         */
        public int size() {
            return N;
        }

       /**
         * Associate key with index i.
         *
         * @param  i an index
         * @param  key the key to associate with index <tt>i</tt>
         * @throws IndexOutOfBoundsException unless 0 &le; <tt>i</tt> &lt; <tt>maxN</tt>
         * @throws IllegalArgumentException if there already is an item
         *         associated with index <tt>i</tt>
         */
        public void insert(int i, Key key) {
            if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
            N++;
            qp[i] = N;
            pq[N] = i;
            keys[i] = key;
            swim(N);
        }

        public int maxIndex() {
            if (N == 0) throw new NoSuchElementException("Priority queue underflow");
            return pq[1];
        }

        public Key maxKey() {
            if (N == 0) throw new NoSuchElementException("Priority queue underflow");
            return keys[pq[1]];
        }

        public int delMax() {
            if (N == 0) throw new NoSuchElementException("Priority queue underflow");
            int min = pq[1];
            exch(1, N--);
            sink(1);

            assert pq[N+1] == min;
            qp[min] = -1;        // delete
            keys[min] = null;    // to help with garbage collection
            pq[N+1] = -1;        // not needed
            return min;
        }

        public Key keyOf(int i) {
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            else return keys[i];
        }

        public void changeKey(int i, Key key) {
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            keys[i] = key;
            swim(qp[i]);
            sink(qp[i]);
        }

        public void change(int i, Key key) {
            changeKey(i, key);
        }

        public void increaseKey(int i, Key key) {
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            if (keys[i].compareTo(key) >= 0)
                throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");

            keys[i] = key;
            swim(qp[i]);
        }
        
        public void decreaseKey(int i, Key key) {
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            if (keys[i].compareTo(key) <= 0)
                throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");

            keys[i] = key;
            sink(qp[i]);
        }

        public void delete(int i) {
            if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
            int index = qp[i];
            exch(index, N--);
            swim(index);
            sink(index);
            keys[i] = null;
            qp[i] = -1;
        }

        private boolean less(int i, int j) {
            return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
        }

        private void exch(int i, int j) {
            int swap = pq[i];
            pq[i] = pq[j];
            pq[j] = swap;
            qp[pq[i]] = i;
            qp[pq[j]] = j;
        }


        private void swim(int k) {
            while (k > 1 && less(k/2, k)) {
                exch(k, k/2);
                k = k/2;
            }
        }

        private void sink(int k) {
            while (2*k <= N) {
                int j = 2*k;
                if (j < N && less(j, j+1)) j++;
                if (!less(k, j)) break;
                exch(k, j);
                k = j;
            }
        }

        public Iterator<Integer> iterator() { return new HeapIterator(); }

        private class HeapIterator implements Iterator<Integer> {
            // create a new pq
            private IndexMaxPQ<Key> copy;

            // add all elements to copy of heap
            // takes linear time since already in heap order so no keys move
            public HeapIterator() {
                copy = new IndexMaxPQ<Key>(pq.length - 1);
                for (int i = 1; i <= N; i++)
                    copy.insert(pq[i], keys[pq[i]]);
            }

            public boolean hasNext()  { return !copy.isEmpty();                     }
            public void remove()      { throw new UnsupportedOperationException();  }

            public Integer next() {
                if (!hasNext()) throw new NoSuchElementException();
                return copy.delMax();
            }
        }

    }
}
