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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
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.LinkedHashSet;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class VK673 {
	public static void main(String[] args) {
//		bearAndGame(System.in);
//		problemsForRound(System.in);
		bearAndColors(System.in);
//		testBearAndColors();
	}
	
	public static void testBearAndColors() {
		Random rand = new Random(0);
		for (int i = 0; i < 10000; i++) {
			for (int len = 1; len < 10; len++) {
				for (int numCol = 1; numCol <= len; numCol++) {
					int[] a = new int[len];
					for (int j = 0; j < a.length; j++) {
						a[j] = rand.nextInt(numCol); 
					}
					
					int[] numDom = new int[a.length+1];
					for (int y = 0; y < a.length; y++) {
						for (int x = y; x < a.length; x++) {
							int[] fcount = new int[a.length+1];
							for (int j = y; j <= x; j++) {
								fcount[a[j]]++;
							}
							int max = 0;
							int maxN = a.length + 10;
							for (int j = 0; j < fcount.length; j++) {
								if (fcount[j] > max || (max == fcount[j] && j < maxN)) {
									max = fcount[j];
									maxN = j;
								}
							}
							numDom[maxN+1]++;
						}
					}
					
					for (int j = 0; j < a.length; j++) {
						a[j]++;
					}
					
					int[] nd2 = bearAndColors(a);
					if (!Arrays.equals(numDom, nd2)) {
						System.out.println("fail");
					}
				}
			}
		}
	}

	public static void bearAndColors(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int[] t = scan.nextIntArray(n);
		int[] numDom = bearAndColors(t);
		
		StringBuilder out = new StringBuilder();
		for (int i = 1; i < numDom.length; i++) {
			if (i > 1) {
				out.append(" ");
			}
			out.append(numDom[i]);	
		}
		System.out.println(out);
	}

	private static int[] bearAndColors(int[] t) {
		int[] numDom = new int[t.length+1];
		for (int y = 0; y < t.length; y++) {
			HashMap<Integer, Integer> map = new HashMap<>();
			int max = 0;
			int maxN = 0;
			for (int x = y; x < t.length; x++) {
				if (x == y) {
					max = 1;
					maxN = t[x];
					map.put(t[x], 1);
					numDom[maxN]++;
				} else {
					if (!map.containsKey(t[x])) {
						map.put(t[x], 1);
					} else {
						map.put(t[x], map.get(t[x]) + 1);
					}
					int currentF = map.get(t[x]);
					if (currentF > max || (currentF == max && t[x] < maxN)) {
						max = currentF;
						maxN = t[x];
					}
					numDom[maxN]++;
				}
			}
		}
		return numDom;
	}

	public static void problemsForRound(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int[] d1 =  new int[m];
		int[] d2 =  new int[m];
		
		int max1 = 1;
		int min2 = n;
		for (int i = 0; i < m; i++) {
			int[] a = scan.nextIntArray(2);
			Arrays.sort(a);
			d1[i] = a[0];
			d2[i] = a[1];
			max1 = Math.max(max1, d1[i]);
			min2 = Math.min(min2, d2[i]);
		}
		
		if (max1 >= min2) {
			System.out.println(0);
		} else {
			System.out.println(min2 - max1);
		}
	}

	public static void bearAndGame(InputStream in) {
		MyScanner scan = new MyScanner(in);
		int n = scan.nextInt();
		int[] x = scan.nextIntArray(n);
		boolean[] watch = new boolean[90];
		int i = 0;
		for (int j = 0; j < 15; j++) {
			if (i+j < watch.length) {
				watch[i+j] = true;
			}
		}
		for (i = 0; i < x.length; i++) {
			for (int j = 0; j < 15; j++) {
				if (x[i]+j < watch.length) {
					watch[x[i]+j] = true;
				}
			}
		}
		int stop = 90;
		for (i = 0; i < watch.length; i++) {
			if (!watch[i]) {
				stop = i;
				break;
			}
		}
		System.out.println(stop);
	}

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner(InputStream in) {
			this.br = new BufferedReader(new InputStreamReader(in));
		}

		public void close() {
			try {
				this.br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

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

		long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = this.nextLong();
			}
			return a;
		}

		int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = this.nextInt();
			}
			return a;
		}

		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;
		}
	}
}
