Description

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.

Input Format

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.

Output Format

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.

4
1 4 8 1
15
1 2 3
1 2 4
1 2 5
1 3 3
1 3 5
1 3 16
1 4 16
1 8 17
1 100 101
1 100 115
1 3 9
2 2
1 3 9
3 4
1 3 9

1
2
-1
0
2
4
3
2
1
-1
3
2
-1

Hint

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