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 t_{i}.

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 $\frac{n \cdot(n + 1)}{2}$ 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 t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ n) where t_{i} 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.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
r=[0]*(n+1)
for i in range(n):
    d={}
    v=-1
    for j in range(i,n):
        t=d.get(a[j],0)+1
        d[a[j]]=t
        if t>v or t==v and a[j]<m:
            v=t
            m=a[j]
        r[m]+=1
print(' '.join(map(str,r[1:])))

n = int(input())
s = [int(i) for i in input().split()]

answer = [0 for i in range(n)]
p = n
for j in range(n):
    a = [0] * p
    domin = s[0]
    answer[domin - 1] += 1
    a[domin - 1] += 1
    for i in range(1, n):
        a[s[i] - 1] += 1
        if a[s[i] - 1] > a[domin - 1] or (a[s[i] - 1] == a[domin - 1] and s[i] < domin):
            domin = s[i]
        answer[domin - 1] += 1
    s.pop(0)
    n -= 1
print(*answer)


n = int(input())
t = [int(q) - 1 for q in input().split()]
k = [0] * n
for i in range(n):
    s = [0] * n
    b = 0
    for a in t[i:]:
        s[a] += 1
        if s[a] > s[b] or a < b and s[a] == s[b]: b = a
        k[b] += 1
print(*k)

n = int(input())
t = [int(q) - 1 for q in input().split()]
k = [0] * n
for i in range(n):
    s = [0] * n
    b = 0
    for a in t[i:]:
        s[a] += 1
        if s[a] > s[b] or a < b and s[a] == s[b]: b = a
        k[b] += 1
print(*k)


class CodeforcesTask643ASolution:
    def __init__(self):
        self.result = ''
        self.ball_count = 0
        self.colors = []

    def read_input(self):
        self.ball_count = int(input())
        self.colors = [int(x) for x in input().split(" ")]

    def process_task(self):
        color_results = [0 for x in range(self.ball_count)]
        for x in range(self.ball_count):
            cl_counts = [0 for x in range(self.ball_count)]
            best = 0
            best_id = -1
            for y in range(x, self.ball_count):
                cl_counts[self.colors[y] - 1] += 1
                if cl_counts[self.colors[y] - 1] > best:
                    best = cl_counts[self.colors[y] - 1]
                    best_id = self.colors[y] - 1
                elif cl_counts[self.colors[y] - 1] == best:
                    if best_id > self.colors[y] - 1:
                        best_id = self.colors[y] - 1
                color_results[best_id] += 1
        self.result = " ".join([str(x) for x in color_results])

    def get_result(self):
        return self.result


def __starting_point():
    Solution = CodeforcesTask643ASolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())

__starting_point()

n = int(input())
t = list(map(int, input().split()))
res = [0] * n
for i in range(n):
    temp = [0] * n
    idx = -1
    max_freq = 0
    for j in range(i, n):
        if temp[t[j] - 1] + 1 > max_freq:
            max_freq += 1
            idx = t[j]
        elif temp[t[j] - 1] + 1 == max_freq and t[j] < idx:
            idx = t[j]
        temp[t[j] - 1] += 1
        res[idx - 1] += 1
print(*res)


# n=int(input())
# n,k=map(int,input().split())
'''l=0
r=10**13
while l+1<r:
    mid=(l+r)//2
    val=(max(0,b_b*mid-b)*rb+max(0,b_s*mid-s)*rs+max(0,b_c*mid-b)*rc)
    if val>money:
        r=mid
    if val<=money:
        l=mid'''
# arr=list(map(int,input().split()))
# n=int(input())
#if all([size%ele==0 for ele,size in s.items()]):
# n,k=map(int,input().split())
# arr=list(map(int,input().split()))
#from collections import Counter
#arr=sorted([(n-int(x),i) for i,x in enumerate(input().split())])
n=int(input())
arr=[int(q)-1 for q in input().split()]
ans=[0]*n
for i in range(n):
    cnt = [0] * n
    best=0
    for j in arr[i:]:
        cnt[j]+=1
        if cnt[j]>cnt[best] or j<best and  cnt[j]==cnt[best] :
            best = j
        ans[best]+=1

print(*ans)