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 CPP):

Solution:
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>

using namespace std;

const long long inf=1e13;

struct RMQ{
	int N;
	long long dat[8192];
	void init(int N_){
		N=1;
		while(N<N_) N*=2;
		for(int i=1;i<=N*2-1;i++) dat[i]=-inf;
	}
	void update(int i,long long x){
		i+=N;
		while(i>0){
			dat[i]=max(dat[i],x);
			i/=2;
		}
	}
	long long get(int i){//[0,i)
		if(i==0) return -inf;
		int le=0,ri=N;
		int k=1;
		long long res=-inf;
		while(ri-le>1){
			int mid=(le+ri)/2;
			if(mid<=i){
				res=max(res,dat[k*2]);
				k=k*2+1;
				le=mid;
			}else{
				k=k*2;
				ri=mid;
			}
		}
		if(ri==i) res=max(res,dat[k]);
		return res;
	}
};


RMQ rmq;

long long sum[4040];
long long dp[4040][4040];

vector<long long> vals;

int N;
long long a[4040];

vector<int> C;

int main(){
	scanf("%lld",&N);
	for(int i=0;i<N;i++) scanf("%lld",a+i);
	sum[0]=a[0];
	for(int i=1;i<N;i++) sum[i]=sum[i-1]+a[i];
	for(int i=0;i<4040;i++) for(int j=0;j<4040;j++){
		dp[i][j]=inf;
	}
	for(int i=0;i<N;i++) dp[i][1]=sum[i];
	for(int k=2;k<=N;k++){
		vals.clear();
		for(int i=0;i<N;i++){
			if(dp[i][k-1]<inf) vals.push_back(dp[i][k-1]+sum[i]);
		}
		sort(vals.begin(),vals.end());
		vals.erase(unique(vals.begin(),vals.end()),vals.end());
		rmq.init(vals.size());
		for(int j=0;j<N;j++){
			int id=distance(vals.begin(),lower_bound(vals.begin(),vals.end(),sum[j]));
			long long ma=rmq.get(id);
			if(ma>-inf){
				dp[j][k]=min(dp[j][k],sum[j]-ma);
			}
			if(dp[j][k-1]<inf){
				id=distance(vals.begin(),lower_bound(vals.begin(),vals.end(),dp[j][k-1]+sum[j]));
				rmq.update(id,sum[j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=N;i++){
		if(dp[N-1][i]<inf){
			ans=i;
		}
	}
	printf("%d\n",ans);
	int cur=N-1;
	for(int i=ans;i>=2;i--){
		bool flg=false;
		for(int j=cur-1;j>=0;j--){
			if(dp[j][i-1]<sum[cur]-sum[j]&&sum[cur]-sum[j]==dp[cur][i]){
				C.push_back(j+1);
				cur=j;
				flg=true;
				break;
			}
		}
		assert(flg);
	}
	reverse(C.begin(),C.end());
	for(int i=0;i<C.size();i++) printf("%d%c",C[i],i==C.size()-1?'\n':' ');
	if(C.size()==0) printf("\n");
//	assert(C.size()>=ans-1);
/*	long long prev=-inf;
	for(int i=0;i<(int)C.size();i++){
		int le=i==0?0:C[i-1];
		//int ri=i==C.size()-1?N-1:C[i+1]-1;
		int ri=C[i];
		long long sum=0;
		for(int j=le;j<ri;j++) sum+=a[j];
	//	assert(prev<sum);
		prev=sum;
	}
	long long xx=0;
	if(C.size()>0){
		for(int i=C[C.size()-1];i<N;i++) xx+=a[i];
	//	assert(prev<xx);
	}*/
	return 0;
}