Get Mean Rank Count

The array is a permutation of 1..n. For each x=1..n, find the number of non-empty contiguous subarrays whose average is exactly x. Different index ranges are counted separately.

输入格式

The first line contains n and the second line contains n distinct ranks. The original bounds are 1≤n≤1000, and the array is exactly a permutation of 1..n, not a general array with duplicate values.

输出格式

Output n integers; the x-th is the number of ranges whose mean is x.

样例 1

输入：

5
1 2 3 4 5

输出：

1 2 3 2 1

样例 2

输入：

4
4 3 2 1

输出：

1 2 2 1

样例 3

输入：

7
4 7 3 6 5 2 1

输出：

1 1 1 4 4 1 1

样例说明

The outputs of the three public examples are 1 2 3 2 1; 1 2 2 1; and 1 1 1 4 4 1 1, checked by independent enumeration or direct simulation.