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.*;

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];
//		TreeSet<Long>[]exist=new TreeSet[n+1];
		for(int i=0; i<=n; i++){
			dp[i]=new TreeMap<Long, Integer>();
			cuts[i]=new HashMap<Long, Integer>();
//			exist[i]=new TreeSet<Long>();
		}
		dp[0]=new TreeMap<Long, Integer>();
		dp[0].put(Long.MIN_VALUE, 0);

		for(int j=1; j<=n; j++){
			if(j%100==0){
//				debug(j, dp[j-1].size());
				// debug(Runtime.getRuntime().totalMemory()/1e6);
			}
			long sum=a[j];
			// dp[j]=new TreeMap<Long, Integer>();
			// cuts[j]=new TreeMap<Long, Integer>();
			for(int i=j-1; i>=0; i--){
				// (i, j]をマージ
				// sum未満で最大のをサーチ
				Entry<Long, Integer> entry=dp[i].lowerEntry(sum);
				if(entry!=null){
					// debug(j,sum);
//					int value=dp[j].containsKey(sum)?dp[j].get(sum):-1;
					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];
			}
			// debug(j, dp[j]);
			// dp[j]の調整
			int max=-1, cut=-1;
			ArrayList<Long> remove=new ArrayList<Long>();
			for(Entry<Long, Integer> entry : dp[j].entrySet()){
				long key=entry.getKey();
				int value=entry.getValue();
				/**
				 * if(entry.getValue()>max){
				 * // そのまま
				 * max=entry.getValue();
				 * cut=cuts[j].get(entry.getKey());
				 * temp.put(entry.getKey(), entry.getValue());
				 * tempCut.put(entry.getKey(), cut);
				 * }else{
				 */
				if(value>max){
					// そのまま
					max=value;
					cut=cuts[j].get(key);
					// dpTemp.put(key, value);
					// cutsTemp.put(key, cut);
				}else{
					// いらん
					// dp[j].put(entry.getKey(), max);
					// cuts[j].put(entry.getKey(), cut);
					remove.add(key);
				}
			}
			for(long key : remove){
				dp[j].remove(key);
				cuts[j].remove(key);
			}
			if(false){
				debug(j, dp[j]);
				debug(j, "cut", cuts[j]);
			}
		}

		LinkedList<Integer> list=new LinkedList<Integer>();
		long sum=Long.MAX_VALUE;
		for(int cut=n; cut>=1;){
			list.addFirst(cut);
			// sum=dp[cut].lastKey();
			sum=dp[cut].lowerKey(sum);
			cut=cuts[cut].get(sum);
		}
		// debug(list);
		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 debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

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

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

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