选择后缀元素的排序¶

预估时间限制：0.5 秒。内存限制：256 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

分拣站有一排带数值标签的货箱。每次指令选出一个货箱及它后方较小的货箱，整理这些位置上的数值。管理员想知道队列还有多少逆序对。

(本故事由GPT-6重写)

给定长度为 \(n\) 的整数数组 \(a\) .逆序对是满足 \(1\le i<j\le n\) 且 \(a_i>a_j\) 的下标对 \((i,j)\) .

一次操作选定位置 \(k\) .以操作开始时的数组为准，取

\[ S=\{k\}\cup\{j:k<j\le n,\ a_j<a_k\}. \]

将这些位置上的数按非降顺序放回这些位置，较小的数放在较小的下标上。其余位置不变。集合包含位置 \(k\) 本身；等于 \(a_k\) 的后继位置不加入集合。

共有 \(m\) 次操作，每次输入整数 \(q\) .若 \(q>0\) ，选取 \(k=q\) ；否则选取

\[ k=((\mathrm{ans}+q)\bmod n)+1, \]

其中 \(\mathrm{ans}\) 是上一次输出，模运算结果在 \(0,\ldots,n-1\) 内。第一次操作使用初始逆序对数作为 \(\mathrm{ans}\) .

第一行两个整数 \(n,m\) .第二行给出 \(a_1,\ldots,a_n\) .接下来 \(m\) 行，每行一个整数 \(q\) .

输出 \(m+1\) 行：初始逆序对数，以及每次操作后的逆序对数。

2
1
1

5
1
1

样例一第一次选位置 \(1,3\) ，数组变为 \((1,3,2)\) ，只剩一个逆序对；再次选位置 \(1\) 不改变数组。样例二第一次选位置 \(1,3,4\) ，得到 \((0,2,1,2)\) ，第二次仍不改变数组。样例三展示负数指令的数学取模。

\(1\le n,m\le100000\) ，\(|a_i|\le10^9\) ，\(q\in[-10^9,-1]\cup[1,n]\) .输入均为整数。

分值比例	额外条件
100%	无额外条件