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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class C {

	int N;
	int[] t,ans;
	int[][] sum,dp;
	public int dfs(int left,int right){

		if(left == right - 1){
			if(dp[left][right] == -1){
				dp[left][right] = t[left];
				ans[t[left]]++;
			}

			return dp[left][right];
		}

		if(dp[left][right] != -1){
			return dp[left][right];
		}

		int leftMin = dfs(left + 1,right);
		int rightMin = dfs(left,right - 1);


		if(sum[right][leftMin] - sum[left + 1][leftMin] < sum[right][t[left]] - sum[left][t[left]]){

			leftMin = t[left];

		}else if(sum[right][leftMin] - sum[left + 1][leftMin] == sum[right][t[left]] - sum[left][t[left]]){

			leftMin = Math.min(leftMin,t[left]);

		}

		if(sum[right - 1][rightMin] - sum[left][rightMin] < sum[right][t[right - 1]] - sum[left][t[right - 1]]){

			rightMin = t[right - 1];

		}else if(sum[right - 1][rightMin] - sum[left][rightMin] == sum[right][t[right - 1]] - sum[left][t[right - 1]]){

			rightMin = Math.min(rightMin, t[right - 1]);

		}

		int ret = Math.min(leftMin, rightMin);
		ans[ret]++;
		return dp[left][right] = ret;
	}

	public void solve() {
		N = nextInt();
		t = new int[N];
		ans = new int[N];
		sum = new int[N + 1][N];
		dp = new int[N][N + 1];

		for(int i = 0;i < N;i++){
			t[i] = nextInt() - 1;
		}

		for(int i = 0;i < N;i++){
			for(int j = 0;j < N;j++){
				sum[i + 1][j] += sum[i][j];
			}

			sum[i + 1][t[i]]++;
		}


		for(int i = 0;i < N;i++){
			for(int j = 0;j < N + 1;j++){
				dp[i][j] = -1;
			}
		}

		dfs(0,N);

		for(int i = 0;i < N;i++){
			if(i != 0)out.print(" ");
			out.print(ans[i]);
		}
		out.println();
	}

	public static void main(String[] args) {
		out.flush();
		new C().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

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

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