You are in charge of Khakha Bank Bashundhara Branch. Your branch has only one desk to serve the customers. There is one employee sitting behind that desk and serving the customers. This employee takes exactly $M$ minutes to serve a customer. Your bank boasts of excellent customer service. You, on the contrary, want to serve the least number of customers possible.
There are $N$ customers standing outside your bank waiting to be served. These customers are numbered $1$ to $N$. You will make them stand in a queue in front of the desk in any order you like before you start serving them. You start serving customers as soon as the line is ready.
For the $i^{th}$ customer, you know his/her waiting time $W_i$ minutes. After waiting in the line for $W_i$ minutes, the $i^{th}$ customer will get frustrated and leave. In other words, the time when the employee starts serving the $i^{th}$ customer customer has to be less than or equal to $W_i$.
While you are thinking about the order of customers in the line, some of their waiting times may change. But you are also a brilliant programmer and this problem is a walk in the park for you. So you code a solution for this problem here.
At any moment, you'll be given an integer $M$ and you have to find the minimum number of customers you need to serve if you line them up in an optimal order.
Input
The first line of the input contains a positive integer $T$ denoting the number of test cases. $T$ cases follow.
The first line of each test case contains a single integer ${N}$. The second line contains ${N}$ integers where the $i^{th}$ integer denotes the waiting time of the $i^{th}$ customer.
The following line contains another integer ${Q}$, which denotes the number of queries to process. Each of the next ${Q}$ lines contain the information of a query of the following two types.
$1$ $P$ $V$: Change the waiting time of the $P^{th}$ customer to $V$.$2$ $M$: Print the minimum number of customers you must serve for this given $M$
Note
The waiting time of the customers will always be distinct before/after any query operation is performed.
Constraints
${1 \leq T \leq 10}$${1 \leq N, Q \leq 50000}$${1 \leq P \leq N}$${1 \leq W_{i}, V, M \leq 10^9}$
Output
For each query of the second type, print the answer in a single line.
Sample
| Input | Output |
|---|---|
1 8 8 10 20 12 11 6 15 18 11 2 5 2 2 2 1 2 3 1 4 25 1 5 16 1 6 22 2 5 2 2 2 1 2 3 | 3 6 7 4 4 6 8 6 |
Explanation
For the first query of the sample case we can arrange the customers in the following order: [18, 15, 20, 12, 11, 6, 10, 8].
Initially the time is 0. Then after serving the first three customers with the waiting times 18, 15 and 20 our current time will become 15. Which is greater than the waiting time of all the remaining customers. So we won't have to serve more than 3 people in this way.
There may have different other ways as well where we'll get the same result too. But there doesn't exist any other optimal order for which we'll be able to serve less than 3 people. Hence the output for the first query is 3.
