지그재그

길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$이 주어진다. 이 수열에는 $1$부터 $N$까지의 정수가 모두 정확히 한 번씩 등장한다.

$A$의 부분수열이란, 수열 $A$에서 0개 이상의 원소를 제거해서 만든 수열을 뜻한다. 세 정수 $x, y, z$ ($1 \le x, y, z \le N$, $y \le z$)가 주어졌을 때, 다음 조건들을 만족하는 $A$의 부분수열이 가질 수 있는 최대 길이를 $f(x, y, z)$라 하자.

1. 부분수열에 들어간 원소들은 원래 위치가 $[y, z]$ 구간에 있어야 한다. 다시 말해, $A_y, A_{y + 1}, \ldots, A_z$의 원소들로만 부분수열을 구성할 수 있다.
2. 부분수열의 모든 원소의 값은 $x$ 이하여야 한다.
3. 부분수열은 지그재그 수열이어야 한다. 길이 $K$인 수열 $S_1, \ldots, S_K$가 지그재그 수열이라는 것은, 각 $i$ ($1 \le i \le K-2$)에 대해 $S_i < S_{i+1}$이라면 $S_{i+1} > S_{i+2}$가, $S_i > S_{i+1}$이라면 $S_{i+1} < S_{i+2}$가 성립한다는 뜻이다. 길이가 2 이하인 수열은 모두 지그재그 수열이다.

길이가 0인 빈 수열은 위 세 조건을 모두 만족하므로, 항상 $f(x, y, z) \geq 0$이다.

$1 \le y \le z \le N$을 만족하는 모든 정수 $y, z$에 대해 $f(x, y, z)$를 모두 합한 값을 $g(x)$로 정의하자. $g(1), g(2), \ldots, g(N)$의 값을 모두 구하는 프로그램을 작성하여라.

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

두 번째 줄에 $A_1, \ldots, A_N$이 공백을 사이에 두고 주어진다.

$N$개의 줄을 출력하라. 이 중 $i$ ($1 \le i \le N$)번째 줄에는 $g(i)$의 값을 출력하라.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 200\,000$
• 모든 $i$ ($1 \le i \le N$)에 대해, $1 \le A_i \le N$.
• 모든 $i, j$ ($1 \le i < j \le N$)에 대해, $A_i \neq A_j$.