Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Subset Trick

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputVanya 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$$$.

Input

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.

Output

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.

Example

Input

3 11 1 2 3 2 1 1 5 1 6 1 7 2 6 2 2 2 3 1 10 2 5 2 7 2 10

Output

4 1 6 12 19 13 8 2 10 3 0 0

Note

In the first example the initial set is $$$S = \{1, 2, 3\}$$$. For this set the trick can be unsuccessful for $$$x \in \{1, 2, 3, 4\}$$$. For example, if $$$x = 4$$$, the volunteer can choose the subset $$$\{1, 2\}$$$ with sum $$$3 \leq x$$$, and can choose the subset $$$\{2, 3\}$$$ with sum $$$5 > x$$$. However, in both cases the illusionist only know the same size of the subset ($$$2$$$), so he can't be sure answering making a guess. Since there is only one subset of size $$$3$$$, and the sum of each subset of smaller size does not exceed $$$5$$$, all $$$x \ge 5$$$ are suitable.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 11:28:48 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|