问题描述

最初有一个长度为 $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$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$。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1 复制

5

1 2 3 4 5

3

1 2

2 2

2 5

样例输出1 复制

3

-1

样例解释1

最初数列为$[1,2,3,4,5]$：

• 对于第一次操作$op = 1,x=2$，则向数列中添加数字 $2$，数列变为$[1,2,3,4,5,2]$；

• 对于第二次操作$op = 2,x=2$，则第一个大于 2 的数为 3；

• 对于第三次操作$op = 2,x=5$，则没有大于 5 的数，输出 −1；

样例输入2 复制

5

1 4 7 5 10

5

1 2

2 2

2 10

1 12

2 10

样例输出2 复制

4

-1

12

样例解释2

最初数列为$[1,4,7,5,10]$：

• 对于第一次操作$op = 1,x=2$，则向数列中添加数字 $2$，数列变为$[1,4,7,5,10,2]$；

• 对于第二次操作 $op = 2,x=2$，则第一个大于 $2$ 的数为 $4$；

• 对于第三次操作 $op = 2,x=10$，没有大于 $10$ 的数，输出 $-1$；

• 对于第四次操作 $op = 1,x=12$，则向数列中添加数字 $12$，数列变为$[1,4,7,5,10,2,12]$；

• 对于第五次操作 $op = 2,x=10$，则第一个大于 $10$的数为$12$。