You are given an array a of N non-negative integers a₁,a₂,…,aₙ (​1​≤​N​≤​2​⋅​10⁵​, ​0​≤​aᵢ​≤​N​). In one operation, you can change any element of a to any non-negative integer.

The mex of an array is the minimum non-negative integer that it does not contain. For each i in the range 0 to N inclusive, compute the minimum number of operations you need in order to make the mex of a equal ​i​.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains ​N​.The next line contains ​a₁,a₂,…,aₙ​.

OUTPUT FORMAT (print output to the terminal / stdout):

For each i in the range 0 to ​N​, output the minimum number of operations for i on a new line. Note that it is always possible to make the mex of a equal to any i in the range 0 to ​N​.

SAMPLE INPUT:

plaintext

4
2 2 2 0

SAMPLE OUTPUT:

plaintext

1
0
3
1
2

• To make the mex of a equal to ​0​, we can change a₄ to 3 (or any positive integer). In the resulting array, ​**[2,2,2,3]**​, 0 is the smallest non-negative integer that the array does not contain, so 0 is the mex of the array.
• To make the mex of a equal to ​1​, we don't need to make any changes since 1 is already the smallest non-negative integer that a=[2,2,2,0] does not contain.
• To make the mex of a equal to ​2​, we need to change the first three elements of ​a​. For example, we can change a to be ​**[3,1,1,0]**​.

SCORING:

• Inputs 2-6: ​N​≤10³
• Inputs 7-11: No additional constraints.