J. Function
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$ and $$$n$$$ quadratic functions with quadratic coefficients equal to $$$1$$$. The $$$i$$$-th function takes the form $$$y=(x-i)^2+b_i$$$ .

Then, you are given a positive integer $$$m$$$ , representing the total number of operations.

There are two types of operations. The first type is to add a quadratic function with a quadratic coefficient of $$$1$$$, taking the form $$$y=(x-a)^2+b$$$ . The second type is query operation, and you should print the minimum function value for all quadratic functions at $$$x=a$$$.

Specifically, for each operation, you will be given the type of the operation first. If the type is $$$0$$$, it represents the first type of operation. If the type is $$$1$$$, it represents the second type of operation. For the first type of operation, you will be given two positive integers $$$a$$$ and $$$b$$$. For the second type of operation, you wil be given one positive integer $$$a$$$.

Input

The first line contains a positive integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, representing the initial number of functions.

The second line contains $$$n$$$ positive integers $$$b_1, b_2, ... , b_{n}$$$ $$$(1 \le b_i \le n)$$$, and the $$$i$$$-th function is $$$y=(x-i)^2+b_i$$$.

The third line contains a positive integer $$$m$$$ $$$(1 \le m \le 10^5)$$$, representing the total number of operations.

Next $$$m$$$ lines, each line contains either "$$$0$$$ $$$a$$$ $$$b$$$" $$$(1 \le a, b\le n)$$$ or "$$$1$$$ $$$a$$$" $$$(1 \le a \le n )$$$, denoting an operation.

Output

Print $$$q$$$ lines where the $$$i$$$-th line contains one integer — the answer for the $$$i$$$-th query operation.

Example
Input
5
2 3 1 3 4
4
1 1
1 2
0 2 1
1 2
Output
2
2
1