Problem: Time passed and Taro became a high school student. Under the influence of my older brother who was a college student, I began to be interested in computer science. Taro read through computer science textbooks and learned that there was a famous problem called the "longest increase subsequence problem." Taro understood this problem, but was wondering if he could create a similar problem himself. Therefore, Taro created the following problem as a result of trial and error.

* There is a sequence A consisting of n integers
* Decompose the sequence A into m sequences with m-1 delimiters. In addition, each sequence after decomposition must always include one or more numbers.
* If the m numbers created by adding all the integers in each of these m sequences are arranged in the order of the original sequence, it becomes a strict increasing sequence (that is, the resulting sequence is Bi <Bi + 1). I want to do it.
* The goal is to maximize the length m of the final sequence B.



For example, consider the case where the sequence A is {5, -4,10, -3,8}.
Prepare a sequence C that represents the position of the delimiter, and set C = {2,4}.
At this time, the sequence A is divided into the parts (5, -4), (10, -3), (8), and when these interiors are added together, they become 1,7,8, respectively, and the resulting sequence B is {1, 7,8}.

<image>

Taro named this problem the "longest increase subsequence problem" and also considered an algorithm to solve it.
And I contacted you as a member of society to check it. Your job is to create a program to solve the problems created by Taro who has grown up.
Since it is my job to check, it also outputs the position of the m-1 delimiter. In addition, there may be multiple such delimiters for the optimum m, but if this m is output correctly, one of the possible ones should be output.

Constraints

> 1 ≤ n ≤ 4000
> | Ai | ≤ 108
>

* For the integer k, | k | represents the absolute value of k

Input

N + 1 integers are given, separated by line breaks.

> n
> A1
> A2
> ...
> An
>

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

Output

> m
> C1 C2 .. Cm-1
>

* The first line outputs one integer m. m represents the length of the final sequence B. The second line outputs m-1 integer Ci separated by blanks. Ci represents the i-th delimiter when the sequence A is appropriately divided into m parts. See the figure for the definition of the delimiter. Note that 1 ≤ Ci <n is satisfied. The m-1 integer sequence C in the second row must be arranged in ascending order. Therefore, if i <j, then Ci <Cj holds.


* If m = 1, the second line will be blank.
* When the sequence B is generated from the sequence A according to the sequence C, when the sequence B is not an increasing sequence (that is, when i (1 ≤ i <m) such that Bi ≥ Bi + 1 exists), it becomes WrongAnswer.

Examples

Input

3
1
2
4


Output

3
1 2


Input

3
2
2
2


Output

2
1


Input

3
4
2
1


Output

1
(空行)

Solution (in JAVA):

Solution:
import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

// Longest Increasing Sequence
// 2012/09/22
public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int n;
	long[] a;

	void run(){
		n=sc.nextInt();
		a=new long[n+1];
		for(int i=0; i<n; i++){
			a[i+1]=sc.nextInt();
		}
		a[0]=Long.MIN_VALUE;
		solve();
	}

	@SuppressWarnings("unchecked")
	void solve(){
		TreeMap<Long, Integer>[] dp=new TreeMap[n+1];
		HashMap<Long, Integer>[] cuts=new HashMap[n+1]; // if use TreeMap,
														// you'll receive TLE,
														// HAHAHA!!!
		for(int i=0; i<=n; i++){
			dp[i]=new TreeMap<Long, Integer>();
			cuts[i]=new HashMap<Long, Integer>();
		}
		dp[0].put(Long.MIN_VALUE, 0);

		for(int j=1; j<=n; j++){
			long sum=a[j];
			for(int i=j-1; i>=0; i--){
				// merge (i, j]
				Entry<Long, Integer> entry=dp[i].lowerEntry(sum);
				if(entry!=null){
					int value=cuts[j].containsKey(sum)?dp[j].get(sum):-1;
					if(entry.getValue()+1>value){
						dp[j].put(sum, entry.getValue()+1);
						cuts[j].put(sum, i);
					}
				}
				sum+=a[i];
			}
			// remove unnecessary entry from dp[j]
			int max=-1;
			ArrayList<Long> remove=new ArrayList<Long>();
			for(Entry<Long, Integer> entry : dp[j].entrySet()){
				long key=entry.getKey();
				int value=entry.getValue();
				if(value>max){
					max=value;
				}else{
					// unnecessary entry
					remove.add(key);
				}
			}
			for(long key : remove){
				dp[j].remove(key);
				cuts[j].remove(key);
			}
		}

		// restore "Longest Increasing Sequence"
		LinkedList<Integer> list=new LinkedList<Integer>();
		int cut;
		long sum;
		for(cut=n, sum=Long.MAX_VALUE; cut>=1;){
			list.addFirst(cut);
			sum=dp[cut].lowerKey(sum);
			cut=cuts[cut].get(sum);
		}
		list.removeLast();
		StringBuilder sb=new StringBuilder();
		sb.append(list.size()+1);
		sb.append('\n');
		for(int i : list){
			sb.append(i);
			sb.append(' ');
		}
		if(sb.charAt(sb.length()-1)==' '){
			sb.deleteCharAt(sb.length()-1);
		}
		println(sb.toString());
	}

	class Scanner{
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in){
			br=new BufferedReader(new InputStreamReader(in));
			eat("");
		}

		void eat(String s){
			st=new StringTokenizer(s);
		}

		String nextLine(){
			try{
				return br.readLine();
			}catch(IOException e){
				throw new IOError(e);
			}
		}

		boolean hasNext(){
			while(!st.hasMoreTokens()){
				String s=nextLine();
				if(s==null)
					return false;
				eat(s);
			}
			return true;
		}

		String next(){
			hasNext();
			return st.nextToken();
		}

		int nextInt(){
			return Integer.parseInt(next());
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}