题目背景

大样例已修复

题目描述

给定序列 $\{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$
$7\sim 10$	$10^6$