# 选择后缀元素的排序

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

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由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$ 行：初始逆序对数，以及每次操作后的逆序对数。

## 样例

### 样例 1

### 输入

```text
3 2
2 3 1
1
1
```

### 输出

```text
2
1
1
```

### 样例 2

### 输入

```text
4 2
2 2 1 0
1
1
```

### 输出

```text
5
1
1
```

### 样例 3

### 输入

```text
4 3
3 -1 3 0
-4
-8
2
```

### 输出

```text
3
3
3
3
```

## 样例解释

样例一第一次选位置 $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% | 无额外条件 |