Do you know why it is so important to correctly make the terms of reference (TOR)? Make yourself comfortable, now we will tell you a horror story about one construction company, which did not pay attention to the TOR.

Once this company built a residential complex which consisted of n high-rise buildings, standing close to each other. The agreement with the customer did not specify the number of floors in each building and the exterior decoration of the walls. Therefore, during q days, the customer changed the requirements, and the construction company had to make changes with already raised buildings. The changes were one of two types:

1. Change the number of floors in the i-th building to x, that is, if there was more floors, then they should be disassembled, and if less—they should be constructed.
2. Change the exterior decoration of the walls of all buildings at the level of the x-th floor. One worker can decorate a continuous segment of buildings, the height of each is at least x floors.

Help the head of the HR department of this company to find out the minimal number of workers that required for each change in the exterior decoration of the walls.

The first line contains an integer n (1 ≤ n ≤ 10⁵) that is the number of buildings.

The second line contains n integers h_i (1 ≤ h_i ≤ 10⁹) that are the original heights of the buildings in the order from left to right.

The third line contains an integer q (1 ≤ q ≤ 10⁵) that is the number of changes.

The following q lines describe the changes in the order in which they were executed. The first number in each line is the type of change (1 or 2).

If the current change has the type 1, then follow the integers i and x (1 ≤ i ≤ n; 1 ≤ x ≤ 10⁹) that are the building number and a new number of its floors accordingly. The buildings are numbered starting with one.

If the current change has the type 2, then follows the integer x (1 ≤ x ≤ 10⁹) that is the height in the floors, at the level of which the change of exterior decoration is required. It is guaranteed that at least one change has type 2.

For each change of type 2, in a separate line output the minimum number of workers which is required to complete the exterior decoration of the walls. Output the answers in order the requests were described.

Illustration of the first three changes of type 2 in the sample: