暂无测试数据。

最初有一个长度为 $n$ 的数列，第 $i$ 个数为 $a_i$。现在蒜头君对数列进行了 $q$ 次操作，对于每次操作：

• 向数列中添加一个数 $x$。
• 询问数列重排序后第一个大于 $x$ 的数是什么，如果没有，则输出 $-1$。

输入格式

第一行输入一个正整数 $n$，代表最初数列的长度。

第二行输入 $n$ 个非负整数，第 $i$个数为 $a_i$，两个数以空格隔开。

接下来输入一个正整数 $q$，表示蒜头君操作的次数。

接下来 $q$ 行，每行两个以空格隔开的整数 op x：

• 若 op == 1，表示向数列中添加一个非负整数 $x$；
• 若 op == 2，表示询问数列中第一个大于 $x$ 的数是什么。

输出格式

对于所有 op == 2 的询问，输出此时数列中第一个大于 $x$ 的数是什么，如果没有，则输出 $-1$。

数据范围

• 对于 $20\%$ 的数据，$1\leq n,q \leq 100$；
• 对于另外 $30\%$ 的数据，$1\leq n \leq 2000,1\leq q\leq 10^5$，其中 op == 1 的次数 $\leq 2000$。
• 对于 $100\%$ 的数据，$1\leq n,q\leq 10^5, 0\leq a_i,x\leq 10^9,1\leq op \leq 2$。

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

3
-1

5
1 4 7 5 10
5
1 2
2 2
2 10
1 12
2 10

4
-1
12