길이가 \(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)\) 의 값을 모두 구하는 프로그램을 작성하여라.

• 주어지는 모든 수는 정수이다.
• \(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 \ne A_j\).

첫 번째 줄에 \(N\)이 주어진다.

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

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 2차 대회 > 중등부 4번 / 고등부 2번