题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

接下来有 $m$ 次操作，操作分为如下两种类型：

• 1 l r x：将下标区间 $[l, r]$ 范围内的所有数字（即 $a_l, a_{l+1}, \ldots, a_r$）的数值都增加 $x$；
• 2 p：查询 $a_p$ 前面 $\gt a_p$ 的最小值，并输出这个数的最小值（即从 $a_1, a_2, \ldots, a_{p-1}$ 中所有大于 $a_p$ 的数中选出数值最小的那个）；如果 $a_p$ 前面没有比 $a_p$ 大的数，则输出 $-1$。

输入格式

第一行，一个整数 $n(1 \le n \le 50000)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 1000)$，表示初始时数列中每个元素的数值。

第三行，一个整数 $m(1 \le m \le 10^5)$，表示操作次数。

接下来 $m$ 行，每行包含一个操作：

• 1 l r x（$1 \le l \le r \le n, 1 \le x \le 1000$）；或
• 2 p（$1 \le p \le n$）。

输出格式

对于每次查询操作 2 p，输出一行，包含一个整数，表示 $a_p$ 前面所有大于 $a_p$ 的数中最小的那个数的数值；如果 $a_p$ 前面的数均不大于 $a_p$，则输出 $-1$ 即可。

样例输入

5
1 2 3 4 5
5
2 4
1 2 3 2
2 4
1 1 3 3
2 5

样例输出

-1
5
7

说明/提示

样例解释

• 初始时数列为 $\{ 1, 2, 3, 4, 5 \}$；
• 第 $1$ 个操作：$a_4 = 4$，前面的数有 $1, 2, 3$，均不大于 $4$，所以输出 $-1$；
• 第 $2$ 个操作：将 $a_2, a_3$ 各增加 $2$，数列变为 $\{ 1, 4, 5, 4, 5 \}$；
• 第 $3$ 个操作：$a_4 = 4$，前面的数有 $1, 4, 5$，其中大于 $4$ 的最小的数只有 $1$ 个 $5$，所以输出 $5$；
• 第 $4$ 个操作：将 $a_1, a_2, a_3$ 各增加 $3$，数列变为 $\{ 4, 7, 8, 4, 5 \}$；
• 第 $5$ 个操作：$a_5 = 5$，前面的数有 $4, 7, 8, 4$，其中大于 $5$ 的数有 $7, 8$，$\min\{ 7, 8 \} = 7$，所以输出 $7$。

数据规模与约定

• 对于 $50\%$ 的数据，$n,m \le 500$
• 对于 $100\%$ 的数据，$1 \le n,m \le 50000; 1 \le a_i, x \le 1000; 1 \le p \le n$