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.

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation


Solutions:
import math
import sys
from collections import Counter

def solve():
	n = int(input())
	T = [int(x) - 1 for x in input().split()]
	M = [[0] * n for i in range(n)]
	(curmin, ans) = ([0] * n, [0] * n)
	for i in range(n):
		ans[T[i]] += 1
		curmin[i] = T[i]
		M[i][T[i]] = 1
	for i in range(n):
		for j in range(i + 1, n):
			M[i][T[j]] += 1
			if M[i][T[j]] > M[i][curmin[i]] or (M[i][T[j]] == M[i][curmin[i]] and T[j] < curmin[i]):
				curmin[i] = T[j]
			ans[curmin[i]] += 1
	return ans
print(' '.join(map(str, solve())))


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())
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(5000.0 + 3)
n = int(input())
res = [0] * N
cum = list(([0] * N for _ in range(N)))
a = list(map(int, input().split()))
for i in range(n):
	c = [0] * N
	for j in range(i, n):
		c[a[j]] += 1
		cum[i][j] = c[a[j]]
for i in range(n):
	(curr_max, curr_idx) = (0, N - 1)
	j = 0
	while cum[i][j] == 0:
		j += 1
	while j < n:
		if cum[i][j] > curr_max or (cum[i][j] == curr_max and a[j] < curr_idx):
			curr_max = cum[i][j]
			curr_idx = a[j]
		res[curr_idx] += 1
		j += 1
print(*res[1:n + 1])


n = int(input())
t = [int(v) for v in input().split()]
ans = [0 for _ in range(n)]
for i in range(n):
	num = [0 for _ in range(n + 1)]
	most_num = 0
	for j in range(i, n):
		num[t[j]] += 1
		if num[t[j]] > num[most_num] or (num[t[j]] == num[most_num] and t[j] < most_num):
			most_num = t[j]
		ans[most_num - 1] += 1
for i in ans:
	print(i, end=' ')


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)


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()


import sys
import math
import itertools as it
import operator as op
import fractions as fr
n = int(sys.stdin.readline().strip())
T = list(map(int, sys.stdin.readline().split()))
cnt = [0 for _ in range(n + 1)]
for i in range(n):
	dom_col = T[i]
	D = [0 for _ in range(n + 1)]
	D[dom_col] = 1
	cnt[dom_col] += 1
	for j in range(i + 1, n):
		col = T[j]
		D[col] += 1
		if D[dom_col] < D[col]:
			dom_col = col
		elif D[dom_col] == D[col]:
			if dom_col > col:
				dom_col = col
		cnt[dom_col] += 1
print(' '.join(map(str, cnt[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)


def main():
	(n, tt) = (int(input()), [])
	res = [0] * n
	for t in map(int, input().split()):
		tt.append(-t)
		(cnt, mx, best_t) = ([0] * n, 0, n)
		for t in reversed(tt):
			cnt[t] += 1
			if (mx, best_t) < (cnt[t], t):
				(mx, best_t) = (cnt[t], t)
			res[best_t] += 1
	print(' '.join(map(str, reversed(res))))
main()


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)


def main():
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	res = [0] * n
	for st in range(n):
		cnt = [0] * n
		x = 0
		y = 0
		for ed in range(st, n):
			cnt[a[ed] - 1] += 1
			if cnt[a[ed] - 1] > x or (cnt[a[ed] - 1] == x and a[ed] - 1 < y):
				x = cnt[a[ed] - 1]
				y = a[ed] - 1
			res[y] += 1
	print(' '.join(map(str, res)))
main()


def solve(n, t):
	sol = [0 for _ in range(n)]
	for i in range(n):
		cts = [0 for _ in range(n + 1)]
		best_c = 0
		for j in range(i, n):
			cts[t[j]] += 1
			if cts[t[j]] > cts[best_c] or (cts[t[j]] == cts[best_c] and t[j] < best_c):
				best_c = t[j]
			sol[best_c - 1] += 1
	return ' '.join(map(str, sol))
n = int(input())
t = [int(v) for v in input().split()]
print(solve(n, t))