지그재그

문제

길이가 $NN$인 수열 $A_1,A_2,\dots ,A_{N}A\_1,\; A\_2,\; \backslash ldots,\; A\_N$이 주어진다. 이 수열에는 $11$부터 $NN$까지의 정수가 모두 정확히 한 번씩 등장한다.

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

1. 부분수열에 들어간 원소들은 원래 위치가 $[y,z][y,\; z]$ 구간에 있어야 한다. 다시 말해, $A_y,A_{y+1},\dots ,A_{z}A\_y,\; A\_\{y\; +\; 1\},\; \backslash ldots,\; A\_z$ 의 원소들로만 부분수열을 구성할 수 있다.
2. 부분수열의 모든 원소의 값은 $xx$ 이하여야 한다.
3. 부분수열은 지그재그 수열이어야 한다. 길이 $KK$ 인 수열 $S_1,\dots ,S_{K}S\_1,\; \backslash ldots,\; S\_K$ 가 지그재그 수열 이라는 것은, 각 $ii$ ($1\le i\le K-21\; \backslash le\; i\; \backslash le\; K-2$)에 대해 이라면 $S_{i+1}>S_{i+2}S\_\{i+1\}\; >\; S\_\{i+2\}$가, $S_i>S_{i+1}S\_i\; >\; S\_\{i+1\}$이라면 가 성립하는 것으로 정의한다. 구체적으로, 길이가 2 이하인 수열은 모두 지그재그 수열이다.

길이가 0인 빈 수열은 위 세 조건을 모두 만족하기 때문에, 항상 $f(x,y,z)\ge 0f(x,\; y,\; z)\; \backslash geq\; 0$ 임에 유의하라.

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

입력

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

두 번째 줄에 $A_1,\dots ,A_{N}A\_1,\; \backslash ldots,\; A\_N$이 공백을 사이에 두고 주어진다.

출력

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

3
1 2 3

3
7
9

6
3 1 4 6 5 2

10
16
22
34
40
46