#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N;
long long X[4001];
int dp[4001][4001], pre[4001][4001];

inline long long key(int i, int j) { return X[j] - X[i]; }
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N) cin >> X[i+1];
  for (int i=0; i<N; i++) X[i+1] += X[i];

  rep(i, N+1) rep(j, N+1) dp[i][j] = -INF, pre[i][j] = -1;
  for (int i=1; i<=N; i++) dp[0][i] = 1, pre[0][i] = 0;
  rep(i, N+1) {
    vector<pair<long long, P> > left, right;
    for (int j=0; j<i; j++)    left.pb(make_pair(key(j, i), P(dp[j][i], j)));
    for (int j=i+1; j<=N; j++) right.pb(make_pair(key(i, j), P(dp[i][j], j)));
    sort(all(left));
    sort(all(right));
    int head = 0;
    P m = P(-INF, -1);
    for (auto p : right) {
      while (head < left.size() && left[head]._1 < p._1) m = max(m, left[head++]._2);
      if (m._1 != -INF) {
        int j = p._2._2;
        assert(dp[i][j] < m._1+1);
        dp[i][j] = m._1+1, pre[i][j] = m._2;
      }
    }
  }

  P m = P(-INF, -1);
  rep(i, N+1) m = max(m, P(dp[i][N], i));
  int m2 = m._2, m1 = m._1;
  vector<int> ans;
  int left = m2, right = N;
  while (left != 0) {
    ans.pb(left);
    int k = left;
    left = pre[left][right];
    right = k;
  }
  reverse(all(ans));
  assert(ans.size() == m1-1);
  cout << m1 << "\n";
  for (int x : ans) cout <<x << " "; cout << "\n";
  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 <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N;
long long X[4001];
int dp[4001][4001], pre[4001][4001];

inline long long key(int i, int j) { return X[j] - X[i]; }
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N) cin >> X[i+1];
  for (int i=0; i<N; i++) X[i+1] += X[i];

  rep(i, N+1) rep(j, N+1) dp[i][j] = -INF, pre[i][j] = -1;
  for (int i=1; i<=N; i++) dp[0][i] = 1, pre[0][i] = 0;
  rep(i, N+1) {
    vector<pair<long long, P> > left, right;
    for (int j=0; j<i; j++)    left.pb(make_pair(key(j, i), P(dp[j][i], j)));
    for (int j=i+1; j<=N; j++) right.pb(make_pair(key(i, j), P(dp[i][j], j)));
    sort(all(left));
    sort(all(right));
    int head = 0;
    P m = P(-INF, -1);
    for (auto p : right) {
      while (head < left.size() && left[head]._1 < p._1) m = max(m, left[head++]._2);
      if (m._1 != -INF) {
        int j = p._2._2;
        assert(dp[i][j] < m._1+1);
        dp[i][j] = m._1+1, pre[i][j] = m._2;
      }
    }
  }

  P m = P(-INF, -1);
  rep(i, N+1) m = max(m, P(dp[i][N], i));
  int m2 = m._2, m1 = m._1;
  vector<int> ans;
  int left = m2, right = N;
  while (left != 0) {
    ans.pb(left);
    int k = left;
    left = pre[left][right];
    right = k;
  }
  reverse(all(ans));
  assert(ans.size() == m1-1);
  cout << m1 << "\n";
  for (int x : ans) cout <<x << " "; cout << "\n";
  return 0;
}
```