[DTOI 2023] B. 去年 11 月卵梦蕾简易钨丝

# 大样例已修复 

给定序列 $\{a_n\}$，支持两种形如 `opt x` 操作： 1. `1 x`：删除一个数 $x$，若序列中没有 $x$，则输出 $-1$ 并跳过本次操作，**若有多个 $x$，则仅删除一个**。 2. `2 x`：向序列中插入一个数 $x$。 **对于每个未被跳过的操作**，试求出 $a$ 的一个排列 $p$，最小化 $\sum \limits_{i=1}^{n} \lvert p_{i+1}-p_i\rvert$ 的值，即最小化 $\lvert p_2-p_1\rvert+\lvert p_3-p_2\rvert+\dots+\lvert p_{n+1}-p_n\rvert$ 的值，其中 $p_{n+1}=p_1$。 **保证任意时刻序列内至少有 $1$ 个数。** --- $p$ 是 $a$ 的排列当且仅当对于 $\forall x$，$\sum [p_i=x]=\sum [a_i=x]$。 简而言之，$p$ 是 $a$ 经过某种方式重排后的结果。 例如 $\{1,1,4,5,1,4\}$ 是 $\{1,5,4,1,4,1\}$ 的一个排列，但是 $\{1,5,4,1,4,7\}$ 不是。

输入共 $q + 2$ 行。 第 $1$ 行两个正整数 $n, q$。 第 $2$ 行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，代表初始的序列。 第 $3 \sim q + 2$ 行，每行两个数 $opt, x$ ， 代表一个询问。

输出有多行。 每行输出 $1$ 个数，代表一个未被忽略的询问的答案，否则输出 `-1`。

5 3
1 2 3 4 10
1 4
1 10
2 9

18
4
16

#### 【样例 1 解释】 对于第一个询问，删除了序列中的数 $4$，则当前序列为$ 1, 2, 3, 10 $， 可以证明 $18$ 为当前序列的最小答案。 对于第二个询问，删除了序列中的数 $10$，则当前序列为$ 1, 2, 3 $， 可以证明 $4$ 为当前序列的最小答案。 对于第三个询问，向序列中添加了一个数 $9$，则当前序列为$ 1, 2, 3, 9 $， 可以证明 $16$ 为当前序列的最小答案。 #### 【样例 2】 见附加文件中的 `abs/abs2.in` 与 `abs/abs2.out`。 该样例满足测试点 $1\sim 4$ 的限制。 #### 【样例 3】 见附加文件中的 `abs/abs3.in` 与 `abs/abs3.out`。 该样例满足测试点 $7\sim 10$ 的限制。 #### 【数据范围与提示】 记 $w$ 为值域大小，对于所有测试数据，保证 $n,q\leq 10^6$，$0\leq w\leq 10^6$。 每个测试点的具体限制见下表： | 测试点编号 | $n,q\leq$ | $w$ | | :----------: | :----------: | :----------: | | $1\sim 4$ | $100$ | $10$ | | $5\sim 6$ | $10^3$ | $10^3$ | | $7\sim 10$ | $10^6$ | $10^6$ |