Burak's lab exam is incoming! The instructors have published an exercise problem for them to work on. However, he is confused about it and wants some help from you.

In the exercise, there is an array of \(\mathbf{N}\) positive integers, and the instructors want to know the number of different integers \(\mathbf{K}\) in the given array. However, they thought this problem was very easy even for the exercise and they added another task.

The solution of the problem should also include \(\mathbf{K}\) numbers; each of which correspond to the number of subarrays of the array with \(k\) different elements in them, for every \(k\) from 1 to \(\mathbf{K}\) (as always, inclusive). So, Burak should find the number of subarrays with \(k\) different numbers for each \(k\) from \(1\) to \(\mathbf{K}\).

Can you help Burak find the \(\mathbf{K}\) and then the \(\mathbf{K}\) numbers of subarrays?

Input

In the first line, integer \(\mathbf{N}\), the length of the array is given.

In the second line the array \(\mathbf{A}\), an array consisting of \(\mathbf{N}\) positive integers is given.

• \(1 \leq \mathbf{N} \leq 500\)
• \(1 \leq \mathbf{A_i} \leq 1000, i \in \mathbf{[0, N-1]}\)

Output

In the first line, print the minimum number of different numbers (\(\mathbf{K}\)) in the given array.

In the second line, print \(\mathbf{K}\) numbers. The \(i^{th}\) number on this line represents the number of subarrays of the given array that have \(i\) different numbers.

Examples

Input 1:

4
2 1 3 1

Output 1:

3
4 4 2

Input 2:

7
4 7 47 74 4 74 4

Output 2:

4
7 9 5 7

Explanation

Input 1

• \([1, 1] = \{ 2 \} \rightarrow 1\)
• \([2, 2] = \{ 1 \} \rightarrow 1\)
• \([3, 3] = \{ 3 \} \rightarrow 1\)
• \([4, 4] = \{ 1 \} \rightarrow 1\)
• \([1, 2] = \{ 2, 1 \} \rightarrow 2\)
• \([2, 3] = \{ 1, 3 \} \rightarrow 2\)
• \([3, 4] = \{ 3, 1 \} \rightarrow 2\)
• \([1, 3] = \{ 2, 1, 3 \} \rightarrow 3\)
• \([2, 4] = \{ 1, 3, 1 \} \rightarrow 2\)
• \([1, 4] = \{ 2, 1, 3, 1 \} \rightarrow 3\)

4 subarrays include 1 different number, 4 subarrays include 2 different numbers and 2 subarrays include 3 different numbers.