길이가 \(N\)인 수열 \(A_1, A_2, . . . , 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}, . . . , A_z\) 의 원소들로만 부분수열을 구성할 수 있다
2. 부분수열의 모든 원소의 값은 \(x\) 이하여야 한다.
3. 부분수열은 지그재그 수열이어야 한다. 길이 \(K\) 인 수열 \(S_1, . . . , 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) \ge 0\) 임에 유의하라.

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

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

두 번째 줄에 \(A_1, . . . , A_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 \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점) 추가 제약 조건 없음