길이가 N인 수열 A_1, A_2, ..., A_N이 주어진다. 이 수열에는 1부터 N까지의 정수가 모두 정확히 한 번씩 등장한다.
A의 부분수열이란, 수열 A에서 0개 이상의 원소를 제거해서 만든 수열을 뜻한다.
세 정수 x, y, z (1 ≤ x, y, z ≤ N, y ≤ 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 < i < K - 2)에 대해 S_{i} < S_{i+1}이라면 S_{i+1} > S_{i+2}가, S > S_i+1이라면 S_{i+1} < S_{i+2}가 성립하는 것으로 정의한다.
구체적으로, 길이가 2 이하인 수열은 모두 지그재그 수열이다.
길이가 0인 빈 수열은 위 세 조건을 모두 만족하기 때문에, 항상 f(x, y, z) ≥ 0 임에 유의하라.
1≤y≤z≤ N를 만족하는 모든 정수 y, z에 대해 f(x, y, z)를 모두 합한 값을 g(x)로 정의하자. g(1), g(2),...,g(N) 의 값을 모두 구하는 프로그램을 작성하여라.
