Background

Original problem link: https://oier.team/problems/S1B。

Problem Description

Children really like candies。

Now, Little K has some candies, and each candy has a number on it representing its type。

There are $q$ events. Each event either adds a candy, removes a candy, or asks a query。

Each query gives an integer $k$, meaning that Little K now needs to distribute all candies to $k$ children, and each child must receive at least one candy. At the same time, children do not like receiving identical candies. Specifically, when a child receives candy type $i$, if they have already received candy type $i$ before that, then they will get very angry, and their anger value increases by $1$。

Little K does not like seeing children angry, but Little K cannot solve such a difficult problem, so you need to help Little K find a way to distribute the candies that minimizes the sum of all children’s anger values。

It is guaranteed that there exists a distribution plan such that every child gets at least one candy。

Each query does not actually perform the distribution, i.e. after each query, the candies owned by Little K do not change。

Note that the candy distribution process can be understood as partitioning all candies owned by Little K into $k$ non-empty sequences, and you may reorder the candies。

Input Format

The first line contains two positive integers $n,q$。

The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$, describing the candies Little K initially has。

The next $q$ lines each contain two positive integers describing an operation. There are three possible inputs:

1 x: Little K gains one more candy of type $x$。

2 x: Little K loses one candy of type $x$. It is guaranteed that at this time Little K has at least one candy of type $x$。

3 k: Little K needs to distribute the candies to $k$ children. You need to output the minimum possible sum of all children’s anger values. Let $S$ be the number of candies Little K currently has, and it is guaranteed that $1\le k\le S$。

Output Format

For each query, output one line with one integer, the answer you computed。

5 4
3 5 2 5 5
3 2
2 5
1 5
3 1

1
2

5 15
2 5 2 5 1
2 1
1 1
1 2
1 4
1 1
3 2
1 1
3 1
1 5
3 1
1 2
3 1
2 1
3 3
2 2

1
5
6
7
1

Hint

Sample Explanation 1

In the first query, the candies in Little K’s hand are $\{3,5,2,5,5\}$. Distribute them to $2$ children as $\{2,3,5\},\{5,5\}$. The children’s anger values are $0,1$. It can be proven that there is no plan with a smaller sum of anger values。

Constraints

This problem uses bundled subtasks for judging。

For $100\%$ of the data, $1\le n,q\le 10^6$, $1\le a_i,x\le n$. In each query, let $S$ be the number of candies Little K currently has, and it is guaranteed that $1\le k\le S$。

Translated by ChatGPT 5