Background

The large sample has been fixed.

Problem Description

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.

Input Format

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.

Output Format

There are multiple lines of output.

Each line outputs $1$ number, representing the answer for a query that is not ignored; otherwise output -1.

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

18
4
16

Hint

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.

Translated by ChatGPT 5