D - バブルソート
Editorial
/
Time Limit: 5 sec / Memory Limit: 512 MB
問題文
高橋君は、毎年誕生日にお母さんから数列をもらっています。 高橋君はバブルソートの交換回数を求めるのが好きなので、毎年、お母さんからもらった数列のバブルソートの交換回数を求めるのを楽しんできました。
しかし今年のお母さんは一味違います。なんと、高橋君がバブルソートの交換回数を求めるのをより一層楽しめるように、とても長い数列を圧縮したものを高橋君に渡したのです。
長さ 10^7 の数列のバブルソートの交換回数なら目視で 1 秒とかからずに求められる高橋君でも、この数列には歯が立ちませんでした。
あなたの仕事は、高橋君に代わってこの数列のバブルソートの交換回数を 10^9+7 で割ったあまり求めることです。
ただし、バブルソートとは、以下の擬似コードで与えられるアルゴリズムです。
input: a[1],...,a[N] for i=1 to N-1 { for j=1 to N-i { if a[j]>a[j+1] swap(a[j],a[j+1]) } }
バブルソートの交換回数とは、上の疑似コードでswapが呼ばれる回数です。
また、圧縮された列からもとの数列を得る方法は、以下の通りです。
- 最初、ポインタは圧縮列の最初の項を指しており、スタックは空である。以下の操作をポインタの位置が圧縮列からはみ出すまで繰り返す。最終的にスタックに残ったひとつの数列が、目的の数列である。
- ポインタの指す値が正なら、スタックにその値の項ひとつからなる数列を積み、ポインタを一つ進める。
- ポインタの指す値が 0 なら、スタックの上から 1 番目と 2 番目の数列を取り出し、後者の後ろに前者をつなげた数列をスタックに積み、ポインタを一つ進める。
- ポインタの指す値が負なら、スタックの一番上の数列を取り出し、それを |ポインタの指す値| 回繰り返したものをスタックに積み、ポインタを一つ進める。
例えば、列
1 2 3 0 -4 5 0 0 -2は数列
1 2 3 2 3 2 3 2 3 5 1 2 3 2 3 2 3 2 3 5を表します。
制約
- N > 0
- -10^5 ≦ A_i ≦ 10^5(1 ≦ i ≦ N)
- A_i ≠ 0 なる i の個数は 10^5 を超えない。
- 与えられる圧縮列からは、上述の方法によって元の数列が復元できることが保障される。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 ... A_N
部分点
この問題には部分点が設定されている。
- 圧縮列の 0 でない要素の個数が 2000 を超えないデータセットに正解した場合、部分点として50点が与えられる。
出力
圧縮列が表す数列のバブルソートの交換回数を 10^9+7 で割った余りを出力せよ。
出力の最後には改行を忘れないこと。
入力例1
9 1 2 3 0 -4 5 0 0 -2
出力例1
45
入力例2
22 12 35 -901 0 43 73 0 -18 2 6 0 -9 428 0 0 0 -23 8 0 -66 2 0
出力例2
509114582