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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Arthur Gazizov  [2oo7] - Kazan FU
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        FastPrinter out = new FastPrinter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, FastScanner in, FastPrinter out) {
            int n = in.nextInt();
            int[] t = in.nextIntArray(n);
            int[] count = new int[n];
            for (int start = 0; start < n; start++) {
                int maxValue = 1123456789;
                int maxCount = -1;
                Counter<Integer> counter = new Counter<>();
                for (int i = start; i < n; i++) {
                    counter.inc(t[i]);
                    int temp = counter.get(t[i]);
                    if (temp > maxCount) {
                        maxCount = temp;
                        maxValue = t[i];
                    } else if (temp == maxCount && maxValue > t[i]) {
                        maxCount = temp;
                        maxValue = t[i];
                    }
                    count[maxValue - 1]++;
                }
            }
            for (int i = 0; i < n; i++) {
                out.prints(count[i]);
            }
        }

    }

    static class FastPrinter extends PrintWriter {
        public FastPrinter(Writer writer) {
            super(writer);
        }

        public FastPrinter(OutputStream out) {
            super(out);
        }

        public FastPrinter prints(int value) {
            print(value);
            print(' ');
            return this;
        }

        public void close() {
            super.close();
        }

    }

    static class Counter<T> extends HashMap<T, Integer> implements Map<T, Integer> {
        public void add(T key, Integer count) {
            if (!containsKey(key)) {
                put(key, 0);
            }
            put(key, get(key) + count);
        }

        public void inc(T key) {
            add(key, 1);
        }

        public Integer get(Object key) {
            Integer ret = super.get(key);
            return ret == null ? 0 : ret;
        }

    }

    static class FastScanner extends BufferedReader {
        boolean isEOF;

        public FastScanner(InputStream is) {
            super(new InputStreamReader(is));
        }

        public FastScanner(InputStreamReader inputStreamReader) {
            super(inputStreamReader);
        }

        public int read() {
            try {
                int ret = super.read();
                if (isEOF && ret < 0) {
                    throw new InputMismatchException();
                }
                isEOF = ret == -1;
                return ret;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

        public static boolean isWhiteSpace(int c) {
            return c >= -1 && c <= 32;
        }

        public int nextInt() {
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int ret = 0;
            while (!isWhiteSpace(c)) {
                if (c < '0' || c > '9') {
                    throw new NumberFormatException("digit expected " + (char) c
                            + " found");
                }
                ret = ret * 10 + c - '0';
                c = read();
            }
            return ret * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public String readLine() {
            try {
                return super.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }

    }
}

