描述

最初有一个长度为 n 的数列，第 i 个数为 a【i】 ​ 。现在小榔头对数列进行了 q 次操作，对于每次操作：

1）向数列中添加一个数 x。

2）询问数列中大于 x 的最小数是什么，如果没有，则输出 −1。

输入

输入文件名为sequence.in。

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

第二行输入 n 个非负整数，第 i个数为 a【i】 ​ ，两个数以空格隔开。

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

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

1）若 op == 1，表示向数列中添加一个非负整数 x；

2）若 op == 2，表示询问数列中大于 x 的最小数是什么。

输出

输出文件名为sequence.out。

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

输入样例 1

5

1 4 7 5 10

5

1 2

2 2

2 10

1 12

2 10

输出样例1

4

-1

12

提示

只能用一个循环