가장 긴 증가 수열

시간이 흘러 타로는 고등학생이 되었다. 대학생인 형의 영향을 받아 컴퓨터 과학에 흥미를 갖기 시작했다. 타로는 컴퓨터 과학 교과서를 읽다가 "최장 증가 부분 수열 문제"라는 유명한 문제가 있다는 것을 알게 되었다. 타로는 이 문제를 이해했지만, 비슷한 문제를 직접 만들어 볼 수는 없을까 궁금해졌다. 그래서 시행착오 끝에 다음과 같은 문제를 만들었다.

• n개의 정수로 이루어진 수열 A가 있다.
• m-1개의 구분점을 넣어 수열 A를 m개의 수열로 나눈다. 나눈 각 수열은 반드시 1개 이상의 수를 포함해야 한다.
• 이 m개 수열 각각에 들어 있는 정수를 모두 더해 얻은 m개의 수를 원래 수열의 순서대로 나열하면 순증가 수열이 되어야 한다. 즉, 결과 수열은 Bi < Bi+1을 만족해야 한다.
• 최종적으로 만들 수 있는 수열 B의 길이 m을 최대로 하는 것이 목표이다.

예를 들어 수열 A가 {5,-4,10,-3,8}인 경우를 생각해 보자. 구분 위치를 나타내는 수열 C를 준비하고 C={2,4}로 둔다. 그러면 수열 A는 (5,-4),(10,-3),(8)로 나뉘고, 각 구간의 합은 1,7,8이 되어 결과 수열 B는 {1,7,8}이 된다.

타로는 이 문제를 "최장 증가 수열 문제"라고 이름 붙이고, 이를 푸는 알고리즘도 생각했다. 그리고 사회인이 된 당신에게 검사를 부탁하는 연락을 했다. 당신의 일은 성장한 타로가 만든 문제를 푸는 프로그램을 작성하는 것이다. 검사가 일이므로 m-1개의 구분 위치도 출력한다. 최적의 m에 대해 이러한 구분 방법이 여러 가지일 수 있지만, 이 m이 올바르게 출력되었다면 가능한 것 중 하나만 출력하면 된다.

줄바꿈으로 구분된 n+1개의 정수가 주어진다.

n 
A1
A2
...
An

• n은 주어지는 수열 A의 길이를 나타낸다.
• Ai는 수열 A의 i번째 원소를 나타낸다.

m
C1 C2 .. Cm-1

• 1번째 줄에는 정수 m 하나를 출력한다. m은 최종적으로 만들 수 있는 수열 B의 길이를 나타낸다. 2번째 줄에는 m-1개의 정수 Ci를 공백으로 구분해 출력한다. Ci는 수열 A를 m개의 부분으로 알맞게 나눴을 때 i번째 구분 위치를 나타낸다. 구분 위치의 정의는 그림을 참고한다. 1≤Ci<n을 만족한다. 2번째 줄의 m-1개 정수열 C는 오름차순으로 나열되어야 한다. 따라서 i < j이면 Ci < Cj가 성립한다.

• m=1인 경우 2번째 줄은 빈 줄이 된다.
• 수열 C에 따라 수열 A에서 수열 B를 생성했을 때, 수열 B가 증가 수열이 아니면(즉, Bi≥Bi+1인 i(1≤i<m)가 존재하면) WrongAnswer가 된다.

• 1≤n≤4000
• |Ai|≤ 108
• 정수 k에 대해 |k|는 k의 절댓값을 나타낸다