{"raw_statement":[{"iden":"background","content":"# 大样例已修复\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/4il8fn7w.png)"},{"iden":"statement","content":"给定序列 $\\{a_n\\}$，支持两种形如 `opt x` 操作：\n\n1. `1 x`：删除一个数 $x$，若序列中没有 $x$，则输出 $-1$ 并跳过本次操作，**若有多个 $x$，则仅删除一个**。\n\n2. `2 x`：向序列中插入一个数 $x$。\n\n**对于每个未被跳过的操作**，试求出 $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$。\n\n**保证任意时刻序列内至少有 $1$ 个数。**\n\n---\n$p$ 是 $a$ 的排列当且仅当对于 $\\forall x$，$\\sum [p_i=x]=\\sum [a_i=x]$。\n\n简而言之，$p$ 是 $a$ 经过某种方式重排后的结果。 \n\n例如 $\\{1,1,4,5,1,4\\}$ 是 $\\{1,5,4,1,4,1\\}$ 的一个排列，但是 $\\{1,5,4,1,4,7\\}$ 不是。"},{"iden":"input","content":"输入共 $q + 2$ 行。\n\n第 $1$ 行两个正整数 $n, q$。\n\n第 $2$ 行 $n$ 个非负整数 $a_1, a_2, \\dots, a_n$，代表初始的序列。\n\t\t\n第 $3 \\sim q + 2$ 行，每行两个数 $opt, x$ ， 代表一个询问。 "},{"iden":"output","content":"输出有多行。\n\n每行输出 $1$ 个数，代表一个未被忽略的询问的答案，否则输出 `-1`。\n\t"},{"iden":"note","content":"#### 【样例 1 解释】\n对于第一个询问，删除了序列中的数 $4$，则当前序列为$ 1, 2, 3, 10 $， 可以证明 $18$ 为当前序列的最小答案。\n\t\n对于第二个询问，删除了序列中的数 $10$，则当前序列为$ 1, 2, 3 $， 可以证明 $4$ 为当前序列的最小答案。\n\t\n对于第三个询问，向序列中添加了一个数 $9$，则当前序列为$ 1, 2, 3, 9 $， 可以证明 $16$ 为当前序列的最小答案。\n\n#### 【样例 2】\n\n见附加文件中的 `abs/abs2.in` 与 `abs/abs2.out`。\n\n该样例满足测试点 $1\\sim 4$ 的限制。\n\n#### 【样例 3】\n\n见附加文件中的 `abs/abs3.in` 与 `abs/abs3.out`。\n\n该样例满足测试点 $7\\sim 10$ 的限制。\n\n#### 【数据范围与提示】\n记 $w$ 为值域大小，对于所有测试数据，保证 $n,q\\leq 10^6$，$0\\leq w\\leq 10^6$。\n\t\n每个测试点的具体限制见下表：\n\n| 测试点编号 | $n,q\\leq$ | $w$ |\n| :----------: | :----------: | :----------: |\n| $1\\sim 4$ | $100$ | $10$ |\n| $5\\sim 6$ | $10^3$ | $10^3$ |\n| $7\\sim 10$ | $10^6$ | $10^6$ |\n"}],"translated_statement":null,"sample_group":[["5 3\n1 2 3 4 10\n1 4\n1 10\n2 9","18\n4\n16"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}