Bessie knows a number x+0.5x+0.5 where xx is some integer between 00 to N,N, inclusive (1≤N≤2⋅1051≤N≤2⋅105).Elsie is trying to guess this number. She can ask questions of the form "is ii high or low?" for some integer ii between 11 and N,N, inclusive. Bessie responds by saying "HI" if ii is greater than x+0.5x+0.5, or "LO" if ii is less than x+0.5x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of NN numbers, where every number from 11 to NN occurs exactly once (in other words, the list is a permutation of size NN). Then she goes through the list, guessing numbers that appear in the list in order.

However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number ii and Elsie previously guessed some j<ij<i and Bessie responded with "HI", Elsie will not guess ii and will move on to the next number in the list. Similarly, if she is about to guess some number ii and she previously guessed some j>ij>i and Bessie responded with "LO", Elsie will not guess ii and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines xx regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string SS, then the number of times Bessie says "HILO" is the number of length 44 substrings of SS that are equal to "HILO."

Bessie knows that Elsie will use this strategy; furthermore, she also knows the exact permutation that Elsie will use. However, Bessie has not decided on what value of xx to choose.

Help Bessie determine how many times she will say "HILO" for each value of xx.

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

The first line contains N.N.The second line contains Elsie's permutation of size N.N.

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

For each xx from 00 to NN, inclusive, output the number of times Bessie will say HILO on a new line.

SAMPLE INPUT:

5
5 1 2 4 3

SAMPLE OUTPUT:

0
1
1
2
1
0

For x=0x=0, Bessie will say "HIHI," for a total of zero "HILO"s.

For x=2x=2, Bessie will say "HILOLOHIHI," for a total of one "HILO".

For x=3x=3, Bessie will say "HILOLOHILO", for a total of two "HILO"s.

SCORING:

• Tests 1 to 4 satisfy N≤5000N≤5000.
• Tests 5 to 8 have a uniformly random permutation.
• Tests 9 to 20 satisfy no further constraints.