Vanya invented an interesting trick with a set of integers.

Let an illusionist have a set of positive integers $S$. He names a positive integer $x$. Then an audience volunteer must choose some subset (possibly, empty) of $S$ without disclosing it to the illusionist. The volunteer tells the illusionist the size of the chosen subset. And here comes the trick: the illusionist guesses whether the sum of the subset elements does not exceed $x$. The sum of elements of an empty subset is considered to be $0$.

Vanya wants to prepare the trick for a public performance. He prepared some set of distinct positive integers $S$. Vasya wants the trick to be successful. He calls a positive number $x$ unsuitable, if he can't be sure that the trick would be successful for every subset a viewer can choose.

Vanya wants to count the number of unsuitable integers for the chosen set $S$.

Vanya plans to try different sets $S$. He wants you to write a program that finds the number of unsuitable integers for the initial set $S$, and after each change to the set $S$. Vanya will make $q$ changes to the set, and each change is one of the following two types:

• add a new integer $a$ to the set $S$, or
• remove some integer $a$ from the set $S$.

The first line contains two integers $n$, $q$ ($1 \leq n, q \leq 200\,000$) — the size of the initial set $S$ and the number of changes.

The next line contains $n$ distinct integers $s_1, s_2, \ldots, s_n$ ($1 \leq s_i \leq 10^{13}$) — the initial elements of $S$.

Each of the following $q$ lines contain two integers $t_i$, $a_i$ ($1 \leq t_i \leq 2$, $1 \leq a_i \leq 10^{13}$), describing a change:

• If $t_i = 1$, then an integer $a_i$ is added to the set $S$. It is guaranteed that this integer is not present in $S$ before this operation.
• If $t_i = 2$, then an integer $a_i$ is removed from the set $S$. In is guaranteed that this integer is present in $S$ before this operation.

Print $q + 1$ lines.

In the first line print the number of unsuitable integers for the initial set $S$. In the next $q$ lines print the number of unsuitable integers for $S$ after each change.