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.
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int max(int a, int b) { return (a > b ? a : b); }
int min(int a, int b) { return (a > b ? b : a); }
void printa(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << ' ';
  }
  cout << "\n";
}
void printv(vector<int> v) {
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << ' ';
  }
  cout << "\n";
}
void printset(set<int> s) {
  for (auto x : s) {
    cout << x << " ";
  }
  cout << "\n";
}
void printmset(multiset<int> s) {
  for (auto x : s) {
    cout << x << " ";
  }
  cout << "\n";
}
void printmgset(multiset<int, greater<int>> s) {
  for (auto x : s) {
    cout << x << " ";
  }
  cout << "\n";
}
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long inf = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;
int fact(int n) { return (n == 1 || n == 0) ? 1 : n * fact(n - 1); }
const int N = 1e6;
void solve() {
  long long n;
  cin >> n;
  vector<long long> v(n);
  vector<long long> ans(n + 1);
  for (long long i = 0; i < (n); ++i) {
    cin >> v[i];
  }
  for (long long i = 0; i < (n); ++i) {
    vector<long long> cnts(5001);
    long long best = v[i];
    cnts[best]++;
    ans[best]++;
    for (long long j = i + 1; j < (n); ++j) {
      cnts[v[j]]++;
      if (cnts[v[j]] > cnts[best] ||
          (cnts[v[j]] == cnts[best] && v[j] < best)) {
        best = v[j];
      }
      ans[best]++;
    }
  }
  for (long long i = 1; i < n + 1; i++) {
    cout << ans[i] << " ";
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  while (t--) {
    solve();
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
