C. Bear and Colors

题目连接：

http://www.codeforces.com/contest/673/problem/C

Description

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 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.

Sample Input

4

1 2 1 2

Sample Output

7 3 0 0

题意

有n个数，然后对于每个区间，这个区间的特征等于这个区间出现次数最多的数，如果有两个数出现的次数一样的话，那么就取较小的那个数

现在问你每个数当了多少次特征

题解：

n才5000，直接n^2枚举就好了，不要犹豫……

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5005;

int n,a[maxn],ans[maxn];

int H[maxn];

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)

    {

        memset(H,0,sizeof(H));

        int ans1=0,ans2=0;

        for(int j=i;j<=n;j++)

        {

            H[a[j]]++;

            if(ans1<H[a[j]]||(ans1==H[a[j]]&&a[j]<ans2))

            {

                ans1=H[a[j]];

                ans2=a[j];

            }

            ans[ans2]++;

        }

    }

    for(int i=1;i<=n;i++)

        printf("%d ",ans[i]);

    printf("\n");

}