HILO

Bessie는 어떤 수 $x+0.5$를 알고 있다. 여기서 $x$는 $0$ 이상 $N$ 이하의 정수이다 ($1\le N\le 2 \cdot 10^5$).

Elsie는 이 수를 맞히려고 한다. Elsie는 $1$ 이상 $N$ 이하의 정수 $i$에 대해 "$i$는 high인가 low인가?"라는 질문을 할 수 있다. Bessie는 $i$가 $x+0.5$보다 크면 "HI"라고, $i$가 $x+0.5$보다 작으면 "LO"라고 답한다.

Elsie는 Bessie의 수를 맞히기 위해 다음과 같은 전략을 세운다. 추측을 시작하기 전에 $1$부터 $N$까지의 모든 수가 정확히 한 번씩 들어 있는 길이 $N$의 수열을 만든다. 즉, 이 수열은 크기 $N$의 순열이다. 그런 다음 수열을 순서대로 훑으며 수열에 나타난 수를 추측한다.

다만 Elsie는 불필요한 추측을 건너뛴다. Elsie가 어떤 수 $i$를 추측하려는데 이전에 어떤 $j < i$를 추측해서 Bessie가 "HI"라고 답한 적이 있다면, Elsie는 $i$를 추측하지 않고 수열의 다음 수로 넘어간다. 마찬가지로 어떤 수 $i$를 추측하려는데 이전에 어떤 $j > i$를 추측해서 Bessie가 "LO"라고 답한 적이 있다면, Elsie는 $i$를 추측하지 않고 수열의 다음 수로 넘어간다. 이 전략을 쓰면 Elsie가 어떤 순열을 만들든 항상 $x$를 유일하게 알아낼 수 있다.

Bessie의 "HI" 또는 "LO" 응답을 모두 이어 붙여 하나의 문자열 $S$를 만들면, Bessie가 "HILO"라고 말한 횟수는 $S$의 길이 $4$ 부분 문자열 중 "HILO"와 같은 것의 개수이다.

Bessie는 Elsie가 이 전략을 쓴다는 것과 Elsie가 사용할 순열이 정확히 무엇인지도 알고 있다. 하지만 어떤 $x$를 고를지는 아직 정하지 않았다.

Bessie가 각 $x$에 대해 "HILO"를 몇 번 말하게 되는지 구하자.

첫째 줄에 $N$이 주어진다.

둘째 줄에 Elsie의 크기 $N$ 순열이 주어진다.

$x$가 $0$부터 $N$까지일 때 Bessie가 HILO를 말하는 횟수를 한 줄에 하나씩 출력한다.