Bessie's HILO Count

Bessie has a number \(x+0.5\), where \(x\) is an integer between \(0\) and \(N\) (with \(1 \le N \le 2\cdot10^5\)). Elsie is trying to guess this number using a fixed permutation of the numbers \(1, 2, \dots, N\). In her strategy she processes the permutation in order. For each number \(a\) in the permutation, she makes a guess if and only if it is not "obviously redundant." In particular, suppose that so far she has made some guesses and recorded Bessie’s responses in a string. She will skip guessing a number \(a\) if either:

• There is an earlier guessed number \(j ( x+0.5\)); or
• There is an earlier guessed number \(j (> a)\) for which Bessie answered \(LO\) (i.e. because \(j < x+0.5\)).

If Elsie actually makes a guess with number \(a\) (i.e. it is not skipped), then Bessie answers according to:

• If \(a \le x\) (recall \(a \le x\) if and only if \(a < x+0.5\)), then Bessie answers LO and Elsie updates her lower bound to \(a\).
• If \(a \ge x+1\) (i.e. \(a > x+0.5\)), then Bessie answers HI and Elsie updates her upper bound to \(a\).

Initially, Elsie starts with bounds \(L=0\) and \(R=N+1\). That is, she only considers a guess \(a\) if \(L < a < R\). Notice that the answer each time is completely determined by comparing \(a\) with \(x\): if \(a \le x\) the answer is LO, otherwise it is HI.

After processing the entire permutation (skipping guesses as needed), let the string of responses be \(S\) (each response is either HI or LO). We define the HILO count of \(S\) as the number of occurrences of the substring HILO (i.e. contiguous subsequences of length 4 that are exactly "HILO").

Your task is: given \(N\) and the permutation that Elsie will use, compute for every possible value of \(x\) (from \(0\) to \(N\)) what Bessie’s HILO count will be if her secret number is \(x+0.5\>.

inputFormat

The first line contains a single integer \(N\) (\(1 \leq N \leq 2\cdot10^5\)). The second line contains \(N\) distinct integers which form a permutation of \(1, 2, \dots, N\).

Note: In the input, the permutation is the order in which Elsie will make her guesses.

outputFormat

Output \(N+1\) lines. The \(i\)-th line (starting from \(i=0\)) should contain a single integer: the HILO count that Bessie will produce if \(x=i\) (i.e. if Bessie's secret number is \(i+0.5\)).

sample

3
3 1 2

0
1
1
0