← 返回题目列表

AtCoder · arc054_d

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的次数。

此外,从压缩序列获得原始序列的方法如下。

  • 最初,指针指向压缩序列的第一项,并且堆栈为空。重复以下操作,直到指针位置超出压缩列之外。保留在堆栈上的单个数字序列是所需的数字序列。
  • 如果指针指向的值为正,则将由该值的一项组成的序列放入堆栈,并且指针前进 1。
  • 指针指向的值为 0 然后从堆栈顶部 1 th 和 2 个数列,将前一个数列放在后一个数列之后入栈,并将指针前进1。
  • 如果指针指向的值为负数,则取栈顶的序列, |ポインタの指す値| 次,重复入栈,指针前进1。

例如,列

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