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.math.BigInteger;
import java.util.*;
 
 
public class Main {
	static HashSet<Integer> set;
	static int count=0;
	static int citi=0;
	static ArrayList<Integer> left=new ArrayList<Integer>();
	static ArrayList<Integer> right=new ArrayList<Integer>();
	static ArrayList<Integer> g[];
	static ArrayList<Integer> ans=new ArrayList<Integer>();
	static long sum=0;
	static long sum1=0;
	static long sum2=0;
	static int  col[];
	static int n;
	static long a[];
	static long b[];
	//static int m;
	static boolean[] visited;
	static int edjes=0;
	static Queue<Integer> Q=new LinkedList<Integer>();
	public static void main(String[] args) throws IOException 
		{
		InputReader in = new InputReader(System.in);
		PrintWriter pw = new PrintWriter(System.out);
//int n=in.nextInt();
		/*
BST b=new BST();
Node root=b.NewNode(1);
root.left=b.NewNode(3);
root.right=b.NewNode(2);
root.left.left=b.NewNode(4);
root.left.right=b.NewNode(5);
root.left.left.left=b.NewNode(6);*/
		int n=in.nextInt();
		int a[]=in.nextIntArray(n);
		int ans[]=new int[5002];
		for(int i=0;i<n;i++)
		{
			int fr[]=new int[5002];
			fr[a[i]]++;
			ans[a[i]]++;
			int max=1;
			int ele=a[i];
			for(int j=i+1;j<n;j++)
			{
				//System.out.println(fr[1]+" "+ans[1]+" "+fr[2]+" "+ans[2]);
				fr[a[j]]++;
				if(fr[a[j]]>max)
				{
					ele=a[j];
					max=fr[a[j]];
					ans[a[j]]++;
				}
				else if(fr[a[j]]==max)
				{
					if(ele>a[j])
					{
						ele=a[j];
						ans[a[j]]++;
					}
					else{
						
						ans[ele]++;
					}
				}
				else
				{
					ans[ele]++;
				}
			//	System.out.println(fr[1]+" "+(i+1)+ " "+(j+1));
			}
		}
		for(int i=1;i<=n;i++)
			System.out.print(ans[i]+" ");
		
		}
	public static boolean check(long cook,int n,long k)
	{
		long sum=0;
		
		for(int i=0;i<n;i++)
		{
			if((cook*a[i])>b[i])
			{
				k-=((cook)*a[i])-b[i];
			}
			if(k<0)break;
		}
		if(k<0)
		return false;
		return true;
	}
	    public static void dfs(int curr,int t)
	    {
	    	visited[curr]=true;
	    	//edjes++;
	    	col[curr]=t;
	    	if(t%2==0)
	    		left.add(curr);
	    	else
	    		right.add(curr);
	    	for(int x:g[curr])
	    	{
	    		edjes++;
	    		if(!visited[x])
	    			dfs(x,t+1);
	    		else
	    		{
	    			if(col[curr]%2==col[x]%2)
	    			{
	    				System.out.println(-1);
	    				System.exit(0);
	    			}
	    		}
	    	}
	    }
	
		/*public static boolean dfs(int curr,int prev)
		{
			vis[curr]=true;
		    int trees=0;
		    for(int x:g[curr])
		    {
		    	if(!vis[x])
		    	{
		    		trees++;
		    		Continue[curr]&=dfs(x,curr);
		    	}
		    }
		  System.out.println(curr+" "+prev+" " +Math.abs(curr-prev)+" "+Continue[5]);
		  if(trees==0)
		  {
			  Continue[curr]=true;
			  if(Math.abs(prev-curr)==1)
				  return true;
			  else
				  return false;
		  }
		  else
		  {
			  if(Continue[curr])
			  {
				  if(Math.abs(prev-curr)==1)
					  return true;
				  else
					  return false;
			  }
			  return false;
		  }
		    
		}
	/*	public static void dfs(int curr,int prev)
		{
			for(int x:g[curr])
			{
				if(x!=prev)
				{
		            dfs(x,curr);
		            val[curr]+=val[x];
					
			    }
			}
		}
	/*	public static boolean dfs2(int curr,int prev)
		{
			for(int x:g[curr])
			{
			    if(x!=prev)
			    {
			    	bool[curr]|=dfs2(x,curr);
			    }
			}
			if(bool[curr])
				return true;
			else if(two[curr].contains(prev)&&(!bool[curr]))
			{
			      ans.add(curr);
		        bool[prev]=true;
				bool[curr]=true;
				return true;
			}
			
			return false;
		}
	*/
		public static long power(long a,long b)
		{
			long result=1;
			while(b>0)
			{
				if(b%2==1)
					result*=a;
				a=a*a;
				b/=2;
			}
			return result;
		}
				public static long pow(long n,long p,long m)
	{
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	}
	static class Pair implements Comparable<Pair>{
		int aud;
		int vid;
		Pair(int mr,int er){
			aud=mr;
			vid=er;
			
		}
		@Override
		public int compareTo(Pair o) {
			return 1;
			}
	}
	public static long gcd(long a, long b) {
		  if (b == 0) return a;
		  return gcd(b, a%b);
		}
	static class InputReader {
 
		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public   int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}