Longest Increasing Sequence

Interview

Time limit5sMemory limit512 MB

Summary

Split a sequence into the maximum number of contiguous blocks whose sums form a strictly increasing sequence, and output the divider positions.

Level: Hard8 of 10
Topics: Dynamic programming, Prefix sum, Greedy, Binary search
Solved: No attempts yet

Problem

Time passed, and Taro became a high school student. Influenced by his older brother, who was a university student, he began to take an interest in computer science. As Taro read through a computer science textbook, he learned that there is a famous problem called the "longest increasing subsequence problem." Taro understood this problem, but he wondered whether he could make a similar problem himself. After some trial and error, he came up with the following problem.

There is a sequence A consisting of n integers.
Insert m-1 dividers to split sequence A into m sequences. Each sequence after the split must contain at least one number.
The m numbers obtained by summing all integers in each of the m sequences, arranged in the order of the original sequence, must form a strictly increasing sequence. That is, the resulting sequence must satisfy Bi < Bi+1.
The goal is to maximize the length m of the sequence B that can ultimately be produced.

For example, consider the case where sequence A is {5,-4,10,-3,8}. Prepare a sequence C representing the divider positions and set C={2,4}. Then sequence A is split into (5,-4),(10,-3),(8); summing each part gives 1,7,8, so the resulting sequence B is {1,7,8}.

Taro named this problem the "longest increasing sequence problem" and also devised an algorithm to solve it. Then he contacted you, now a working adult, to ask you to check it. Your job is to write a program that solves the problem made by Taro, who has grown up. Since checking is the job, you also output the positions of the m-1 dividers. For an optimal m, there may be multiple such ways to divide; as long as this m is output correctly, outputting any one of the possible ways is fine.

Input

n+1 integers are given, separated by newlines.

n 
A1
A2
...
An

n represents the length of the given sequence A.
Ai represents the i-th element of sequence A.

Output

m
C1 C2 .. Cm-1

The first line contains a single integer m. m represents the length of the sequence B that can ultimately be produced. The second line contains m-1 integers Ci separated by spaces. Ci represents the i-th divider position when sequence A is properly split into m parts. See the figure for the definition of a divider position. It satisfies 1≤Ci<n. The sequence C of m-1 integers on the second line must be sorted in ascending order. Therefore, if i < j, then Ci < Cj holds.

If m=1, the second line is an empty line.
When sequence B is generated from sequence A according to sequence C, if sequence B is not an increasing sequence (that is, if there exists an i(1≤i<m) with Bi≥Bi+1), the result is WrongAnswer.

Constraints

1≤n≤4000
|Ai|≤ 108
For an integer k, |k| represents the absolute value of k

Examples3

Example 1
Input
```
3
1
2
4
```
Expected output
```
3
1 2
```
Example 2
Input
```
3
2
2
2
```
Expected output
```
2
1
```
Example 3
Input
```
3
4
2
1
```
Expected output
```
1
```