AtCoder Regular Contest 054

D - バブルソート


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 524.288MB

問題文

高橋君は、毎年誕生日にお母さんから数列をもらっています。 高橋君はバブルソートの交換回数を求めるのが好きなので、毎年、お母さんからもらった数列のバブルソートの交換回数を求めるのを楽しんできました。

しかし今年のお母さんは一味違います。なんと、高橋君がバブルソートの交換回数を求めるのをより一層楽しめるように、とても長い数列を圧縮したものを高橋君に渡したのです。

長さ 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

Submit提出する