#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  vector<T> dat;
  // 要素数、結合演算、作用素の適用演算、台集合の単位元、初期値
  SegmentTree(int n_,F f,G g,T d1,
        vector<T> v=vector<T>()){
    this->f=f;
    this->g=g;
    this->d1=d1;
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(int a,int b){
    return query(a,b,0,0,n);
  }
};

ll N;
ll A[4001];
ll dp[2][4001];
ll pre[4001][4001];
ll sum[4001];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>N;
  rep(i,N)cin>>A[i];
  rep(i,N){
    sum[i+1]=sum[i]+A[i];
  }
  rep(i,2)rep(j,N+1){
    dp[i][j]=INF;
  }
  rep(i,N+1)rep(j,N+1){
    pre[i][j]=-1;
  }
  ll crt=0,nxt=1;
  dp[crt][0]=-INF;
  ll ans=0;
  rep(i,N){
    SegmentTree<P,P> sgt(N+1,[](P a,P b){return min(a,b);},[](P a,P b){return b;},P(INF,INF));
    vector<P> vs;
    rep(j,N+1){
      vs.push_back(P(dp[crt][j]+sum[j],j));
      dp[nxt][j]=INF;
    }
    sort(all(vs));
    rep(j,N+1){
      ll k=lower_bound(all(vs),P(sum[j],-INF))-vs.begin();
      P p=sgt.query(0,k);
      if(p.fi!=INF){
        if(j==N){
          ans=i+1;
        }
        dp[nxt][j]=p.fi+sum[j];
        pre[i+1][j]=p.se;
      }

      k=lower_bound(all(vs),P(dp[crt][j]+sum[j],j))-vs.begin();
      sgt.update(k,P(-sum[j],j));
    }
    swap(crt,nxt);
  }
  P crtp=P(ans,N);
  vector<ll> res;
  while(P(crtp.fi-1,pre[crtp.fi][crtp.se])!=P(-1,-1)){
    res.push_back(crtp.se);
    crtp=P(crtp.fi-1,pre[crtp.fi][crtp.se]);
  }
  reverse(all(res));
  cout<<ans<<endl;
  if(res.size()>1){
    cout<<res[0];
    repl(i,1,res.size()-1)cout<<" "<<res[i];
    cout<<endl;
  }

  return 0;
}


### Prompt

Please provide a cpp coded solution to the problem described below:

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
(空行)

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  vector<T> dat;
  // 要素数、結合演算、作用素の適用演算、台集合の単位元、初期値
  SegmentTree(int n_,F f,G g,T d1,
        vector<T> v=vector<T>()){
    this->f=f;
    this->g=g;
    this->d1=d1;
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  T query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(int a,int b){
    return query(a,b,0,0,n);
  }
};

ll N;
ll A[4001];
ll dp[2][4001];
ll pre[4001][4001];
ll sum[4001];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>N;
  rep(i,N)cin>>A[i];
  rep(i,N){
    sum[i+1]=sum[i]+A[i];
  }
  rep(i,2)rep(j,N+1){
    dp[i][j]=INF;
  }
  rep(i,N+1)rep(j,N+1){
    pre[i][j]=-1;
  }
  ll crt=0,nxt=1;
  dp[crt][0]=-INF;
  ll ans=0;
  rep(i,N){
    SegmentTree<P,P> sgt(N+1,[](P a,P b){return min(a,b);},[](P a,P b){return b;},P(INF,INF));
    vector<P> vs;
    rep(j,N+1){
      vs.push_back(P(dp[crt][j]+sum[j],j));
      dp[nxt][j]=INF;
    }
    sort(all(vs));
    rep(j,N+1){
      ll k=lower_bound(all(vs),P(sum[j],-INF))-vs.begin();
      P p=sgt.query(0,k);
      if(p.fi!=INF){
        if(j==N){
          ans=i+1;
        }
        dp[nxt][j]=p.fi+sum[j];
        pre[i+1][j]=p.se;
      }

      k=lower_bound(all(vs),P(dp[crt][j]+sum[j],j))-vs.begin();
      sgt.update(k,P(-sum[j],j));
    }
    swap(crt,nxt);
  }
  P crtp=P(ans,N);
  vector<ll> res;
  while(P(crtp.fi-1,pre[crtp.fi][crtp.se])!=P(-1,-1)){
    res.push_back(crtp.se);
    crtp=P(crtp.fi-1,pre[crtp.fi][crtp.se]);
  }
  reverse(all(res));
  cout<<ans<<endl;
  if(res.size()>1){
    cout<<res[0];
    repl(i,1,res.size()-1)cout<<" "<<res[i];
    cout<<endl;
  }

  return 0;
}


```