60041 지그재그 Diamond V

문제

길이가 $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$.

서브태스크

번호	배점	제한
1	10	$N \le 15$.
2	13	$N \le 100$.
3	17	$N \le 500$.
4	22	$N \le 5\,000$.
5	38	추가 제약 조건 없음.

3
1 2 3

3
7
9

6
3 1 4 6 5 2

10
16
22
34
40
46