Problem J
Jumping Choreography

As you may know, the frogs are the biggest show-offs of the entire animal kingdom. Some weeks ago, they greatly impressed the other animals by forming a large tower. However, the frog king wants to surpass this performance at the next Benelux Amphibian Pillaring Ceremony (BAPC). He wants the frogs to perform a difficult dance which will end in a climax where all frogs form a tower. You have been appointed choreographer and will practice with the frogs in the following months.

A frog dance is a form of line dance: a certain number of frogs line up and then perform a sequence of jumps, where every jump is either to the left or the right. The frog king decided to make this particular dance more interesting. Firstly, he dictated that the frogs have to increase the length of each jump. This means that for any frog, its first jump will be of length $1$, the second of length $2$, the third of length $3$, and so on. Secondly, the dance should end with all frogs on one big tower. Thirdly, the total number of jumps that the frogs make should be as low as possible, in order to make the dance flashy and impressive-looking.

Since the king is a perfectionist, he wants the dance to be flawless. He has provided you with a team of excellent frog dancers, their starting positions, and the place he wants the frogs to form a tower at the end of the dance. However, the king still isn’t convinced that the dance will be as perfect as he wants it to be, so he visits the rehearsal every day in order to make a change: he might find another frog that is very good at dancing and add it to the line-up, or he might feel that a frog is not good enough and remove him/her. He can even change the position of the final tower if he feels like it.

At the end of every day, the frog king wants to see the dance performed in the most efficient way possible, i.e. with the lowest total number of jumps.

Input

• A single line containing two integers $0 \leq n \leq 5000$ and $0\leq t\leq 10^6$, the initial number of frogs and the initial position of the frog tower.

• The second line contains $n$ integers $0\leq p_ i\leq 10^6$, the starting positions of these frogs.

• Then follows a line with an integer $0\leq C\leq 10^6$, the number of changes the king makes.

• $C$ lines follow, each of one of the following three forms.

  • A line of the form $+$ $a$ indicates that the king adds a frog at position $a$.

  • A line of the form $-$ $a$ indicates that the king removes a frog from position $a$. You may assume that at least one frog started from this position before removing it.

  • A line of the form $\mathrm t$ $a$ indicates that the king changes the position of the frog tower to $a$.

  In each case $a$ is between $0$ and $10^6$ inclusive. It is guaranteed that the number of times the kings adds or removes a frog is at most $5000$.

Output

For each of the $C$ modifications, print one line containing the lowest total number of jumps of the dance after applying the modification.

1 1
0
7
t 0
t 1
t 2
t 3
t 4
t 5
t 6

0
1
3
2
3
5
3

3 0
2 6 6
10
t 1
t 2
t 3
t 4
t 5
t 6
t 7
t 8
t 9
t 10

11
6
5
9
4
3
7
9
9
10

0 0

7
t 3
+ 4
t 5
+ 6
t 2
- 4
t 1

0
1
1
2
6
3
5