Tricky Password

3000ms

524288K

Description:

In order to ensure confidentiality, the access to the "Russian Code Cup" problems is password protected during the problem development process.

To select a password, the jury can generate a special table that contains n columns and the infinite number of rows. To construct a table, the first row is fixed, and all the others are obtained by the following rule:

In the row i at position p there is a number equal to the number of times a[i - 1][p] occurs on the prefix a[i - 1][1... p].

To ensure the required level of confidentiality, the jury must be able to perform the following operations:

Replace number a[1][p] by v and rebuild the table.
Find the number a[x][y], which will be the new password.

Doing all these steps manually is very tedious, so the jury asks you to help him. Write a program that responds to the request of the jury.

Input:

The first line contains an integer n (1 ≤ n ≤ 100000) — the number of columns. The second line contains the description of the first row of the table, that is, n integers, which are not less than 1 and do not exceed 10⁹.

The third line of the input contains an integer m (1 ≤ m ≤ 100000) — the number of requests.

Next, each row contains a description of the request, which consists of three integers:

If the first number is equal to 1, then the remaining two numbers are v, p (1 ≤ v ≤ 10⁹; 1 ≤ p ≤ n). So, you should put value v in the position p in the first row.
If the first number is equal to 2, then the remaining two numbers are x, y (1 ≤ x ≤ 10⁵; 1 ≤ y ≤ n) — the row and column of the table cell from which you want to get value.

Output:

Print an answer for each request of the second type in the order you receive them.

Sample Input:

6
1 2 2 2 3 1
3
2 2 3
1 3 3
2 3 4

Sample Output:

2
1

Informação

Provedor Codeforces

Código CF418E