P5986 [PA 2019] Szprotki i szczupaki

There are $n$ small fish in a lake. The weight of the $i$-th small fish is $w_i$. There are $q$ operations. Each operation is one of the following $3$ types: - `1 s k` Suppose a big shark with weight $s$ arrives now. Its goal is to make its weight at least $k$ (including $k$). Ask for the minimum number of small fish it needs to eat. If the shark’s current weight is strictly greater than the weight $w$ of a small fish, then it can eat that fish and increase its own weight by $w$. - `2 w` Add a small fish with weight $w$. - `3 w` Delete a small fish with weight $w$. It is guaranteed that at least one such fish exists.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $w_1, w_2, ..., w_n$. The third line contains a positive integer $q$. The next $q$ lines each contain several integers describing an operation.

For each query, if there is a solution, output one integer per line: the minimum number of small fish that need to be eaten. If there is no solution, output `-1`.

For $100\%$ of the testdata, $1 \le w_i \le 10^{12}$, $1 \le s, k \le 10^{18}$, $1 \le w \le 10^{12}$, $1 \le n \le 3 \times 10^5$, $1 \le q \le 10^5$. Translated by ChatGPT 5