AT_arc054_d [ARC054D] バブルソート

[problemUrl]: https://atcoder.jp/contests/arc054/tasks/arc054_d 高橋君は、毎年誕生日にお母さんから数列をもらっています。 高橋君はバブルソートの交換回数を求めるのが好きなので、毎年、お母さんからもらった数列のバブルソートの交換回数を求めるのを楽しんできました。 しかし今年のお母さんは一味違います。なんと、高橋君がバブルソートの交換回数を求めるのをより一層楽しめるように、とても長い数列を圧縮したものを高橋君に渡したのです。 長さ $ 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 $ $ A_1 $ ... $ A_N $

圧縮列が表す数列のバブルソートの交換回数を $ 10^9+7 $ で割った余りを出力せよ。 出力の最後には改行を忘れないこと。

### 制約 - $ N\ >\ 0 $ - $ -10^5\ ≦\ A_i\ ≦\ 10^5(1\ ≦\ i\ ≦\ N) $ - $ A_i\ ≠\ 0 $ なる $ i $ の個数は $ 10^5 $ を超えない。 - 与えられる圧縮列からは、上述の方法によって元の数列が復元できることが保障される。 - 入力はすべて整数である。 ### 部分点 この問題には部分点が設定されている。 - 圧縮列の $ 0 $ でない要素の個数が $ 2000 $ を超えないデータセットに正解した場合、部分点として$ 50 $点が与えられる。