P8939 [DTOI 2023] B. Last November’s “Luanmenglei” Simple Tungsten Wire.

# The large sample has been fixed. 

Given a sequence $\{a_n\}$, it supports two types of operations of the form `opt x`. 1. `1 x`: Delete one number $x$. If there is no $x$ in the sequence, output `-1` and skip this operation. **If there are multiple $x$, delete only one of them**. 2. `2 x`: Insert one number $x$ into the sequence. **For each operation that is not skipped**, find a permutation $p$ of $a$ that minimizes $\sum \limits_{i=1}^{n} \lvert p_{i+1}-p_i\rvert$, that is, minimize $\lvert p_2-p_1\rvert+\lvert p_3-p_2\rvert+\dots+\lvert p_{n+1}-p_n\rvert$, where $p_{n+1}=p_1$. **It is guaranteed that at any time there is at least $1$ number in the sequence.** --- $p$ is a permutation of $a$ if and only if for all $x$, $\sum [p_i=x]=\sum [a_i=x]$. In short, $p$ is the result of rearranging $a$ in some way. For example, $\{1,1,4,5,1,4\}$ is a permutation of $\{1,5,4,1,4,1\}$, but $\{1,5,4,1,4,7\}$ is not.

The input has $q + 2$ lines in total. Line $1$ contains two positive integers $n, q$. Line $2$ contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, representing the initial sequence. Lines $3$ to $q + 2$ each contain two numbers $opt, x$, representing one query.

There are multiple lines of output. Each line outputs $1$ number, representing the answer for a query that is not ignored; otherwise output `-1`.

#### Sample 1 Explanation. For the first query, the number $4$ is deleted from the sequence, so the current sequence is $1, 2, 3, 10$. It can be proven that $18$ is the minimum answer for the current sequence. For the second query, the number $10$ is deleted from the sequence, so the current sequence is $1, 2, 3$. It can be proven that $4$ is the minimum answer for the current sequence. For the third query, the number $9$ is added to the sequence, so the current sequence is $1, 2, 3, 9$. It can be proven that $16$ is the minimum answer for the current sequence. #### Sample 2. See `abs/abs2.in` and `abs/abs2.out` in the additional files. This sample satisfies the constraints of test points $1\sim 4$. #### Sample 3. See `abs/abs3.in` and `abs/abs3.out` in the additional files. This sample satisfies the constraints of test points $7\sim 10$. #### Constraints and Hints. Let $w$ be the value range size. For all testdata, it is guaranteed that $n,q\leq 10^6$ and $0\leq w\leq 10^6$. The specific constraints for each test point are shown in the table below. | Test Point ID | $n,q\leq$ | $w$ | | :----------: | :----------: | :----------: | | $1\sim 4$ | $100$ | $10$ | | $5\sim 6$ | $10^3$ | $10^3$ | | $7\sim 10$ | $10^6$ | $10^6$ | Translated by ChatGPT 5