P7988 [USACO21DEC] HILO G

Bessie has a number $x+0.5$, where $x$ is an integer between $0$ and $N$ ($1\le N\le 2 \cdot 10^5$). Elsie is trying to guess this number. She can ask questions of the following form for some integer between $1$ and $N$: “Is $i$ too big or too small?” If $i$ is greater than $x+0.5$, Bessie answers "HI"; if $i$ is less than $x+0.5$, she answers "LO". Elsie comes up with the following strategy to guess Bessie’s number. Before making any guesses, she creates a sequence containing $N$ integers, where each number from $1$ to $N$ appears exactly once (in other words, the sequence is a permutation of length $N$). Then she goes through this list and makes guesses in the order of the numbers in the list. However, Elsie will skip all unnecessary guesses. That is, if Elsie is about to guess some number $i$, but earlier she has already guessed some $j < i$ and Bessie answered "HI", then Elsie will not guess $i$ and will instead continue to the next number in the sequence. Similarly, if she is about to guess some number $i$, but earlier she has already guessed some $j > i$ and Bessie answered "LO", then Elsie will not guess $i$ and will instead continue to the next number in the sequence. It can be proven that with this strategy, for any sequence Elsie creates, she can uniquely determine $x$. If we concatenate all of Bessie’s answers ("HI" or "LO") into a string $S$, then the number of times Bessie says "HILO" is the number of length $4$ substrings of $S$ that are equal to "HILO". Bessie knows that Elsie will use this strategy; moreover, she also knows the permutation Elsie will use. However, Bessie has not yet decided which value of $x$ to choose. Help Bessie compute, for each value of $x$, how many times she will say "HILO".

The first line contains $N$. The second line contains Elsie’s permutation of length $N$.

For each $x$ from $0$ to $N$, output one line containing the number of times Bessie will say HILO.

[Sample Explanation] For $x=0$, Bessie will say "HIHI", for a total of $0$ occurrences of "HILO". For $x=2$, Bessie will say "HILOLOHIHI", for a total of $1$ occurrence of "HILO". For $x=3$, Bessie will say "HILOLOHILO", for a total of $2$ occurrences of "HILO". [Constraints] - Testcases 1-4 satisfy $N \leq 5000$. - Testcases 5-8 are uniformly random permutations. - Testcases 9-20 have no additional constraints. Translated by ChatGPT 5