Candy Distribution Minimization

Little children love candies. Now, Little K has some candies, and each candy has a number indicating its type. There are \(q\) events. In each event, a candy can be added, removed, or a query can be made.

For a query event, you are given an integer \(k\) which indicates that Little K needs to distribute all the candies among \(k\) children such that each child gets at least one candy. Moreover, children do not like to receive the same type of candy more than once. Specifically, if a child receives a candy of type \(i\) and has already received a candy of type \(i\) before, then the child's anger increases by \(1\).

Your task is to help Little K by finding a distribution of candies that minimizes the total anger of all children. Note that after each query the distribution does not actually change the candies Little K owns.

Important: The distribution can be thought of as partitioning all the candies into \(k\) non-empty sequences, and the candies within each sequence may be rearranged arbitrarily.

Hint: For each candy type with frequency \(f\), if you distribute them among \(k\) children to avoid duplicates as much as possible, the minimal anger contributed by that type is \(\max(0, f - k)\). Thus, the answer for a query is \(\sum_{\text{type}} \max(0, f - k)\).

inputFormat

The first line contains an integer \(q\) \((1 \le q \le 10^5)\) representing the number of events. Each of the next \(q\) lines contains an event in one of the following formats:

• + x: Add a candy of type x (\(x\) is an integer).
• - x: Remove one candy of type x (it is guaranteed that at least one candy of type x exists).
• ? k: Query the minimal total anger when distributing all candies to \(k\) children (\(1 \le k \le n\), where \(n\) is the current number of candies). It is guaranteed that a valid distribution exists.

outputFormat

For each query event, output one line containing a single integer --- the minimal total anger value when distributing the candies.

sample

6
+ 1
+ 1
+ 2
? 2
- 1
? 1

0
0