Longest Increasing Sequence

時は過ぎて太郎君は高校生になりました。大学生だったお兄さんの影響も受け、コンピューターサイエンスに興味を持ち始めました。太郎君はコンピューターサイエンスの教科書を読み進め、「最長増加部分列問題」という有名問題があることを知りました。太郎君はこの問題のことを理解しましたが、自分でも類似問題が作れないものかと気になりました。そこで太郎君は試行錯誤の結果に次のような問題を作りました。

n個の整数で構成される数列Aがある
m-1個の区切りを入れて、数列Aをm個の数列に分解する。なお、分解後のそれぞれの数列は1つ以上の数を必ず含まなければならない。
このm個それぞれの数列内の整数をすべて足し合わせた結果出来上がるm個の数を、元の数列の順に配置すると厳密な増加列になっている(つまり、出来上がる数列はBi < Bi+1をみたす)ようにしたい。
目標は最終的にできる数列Bの長さmを最大化することである。

例えば、数列Aが{5,-4,10,-3,8}の場合を考えてみる。区切りの位置を表す数列Cを用意し、C={2,4}とする。このとき、数列Aは(5,-4),(10,-3),(8)の部分に分かれ、これらの内部を足し合わせるとそれぞれ1,7,8となり、出来上がる数列Bは{1,7,8}となる。

太郎君はこの問題について"最長増加列問題"と名付け、これを解くアルゴリズムも考えました。そして社会人になったあなたにチェックをしてほしいと連絡をしました。あなたの仕事は、成長した太郎君の作った問題を解くプログラムを作ることです。チェックするのが仕事なので、m-1個の区切りの位置も出力します。なお、最適なmに対してこのような区切り方が複数考えられる場合もありますが、このmが正しく出力されていれば、考えられるもののうち一つを出力すればよいです。

m
C1 C2 .. Cm-1

1行目は一つの整数mを出力する。 mは最終的にできる数列Bの長さを表す。 2行目はm-1個の整数Ciを空白区切りで出力する。 Ciは、数列Aをm個の部分に適切に区切った時のi番目の区切り場所を表す。区切り場所の定義は図を参照せよ。なお、1≤Ci<n を満たす。 2行目のm-1個の整数列Cは昇順に並んでいなければならないしたがって、i < j ならば Ci < Cj が成立する。

m=1の場合2行目は空行になる。
数列Cに従って数列Aから数列Bを生成したとき、数列Bが増加列になっていないとき(すなわちBi≥Bi+1となるi(1≤i<m)が存在するとき)、WrongAnswerとなる

Longest Increasing Sequence

문제

입력

출력

제한