問題文
高桥每年生日都会收到他母亲发来的数字序列。 高桥喜欢求改变冒泡排序的次数,因此他非常享受母亲每年给他的数列冒泡排序的求改变次数。
但是今年的妈妈有点不同。为了让高桥在冒泡排序中查找交换次数变得更加有趣,我给了他一个很长的数字序列的压缩版本。
长度 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