题目描述

给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足：

则称 $b$ 是 $a$ 数列的幻数。

接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整数 $k_i$，每次修改都会对后面的询问产生影响。你需要求出第一次修改前以及每次修改后这个数列的最小的幻数是多少，特别的，如果不存在幻数请输出 $-1$。

输入格式

第一行一个整数 $n$ 表示数列长度。

第二行 $n$ 个整数表示整数数列 $a$。

第三行一个整数 $q$ 表示询问次数。

接下来 $q$ 行每行两个整数 $u_i,k_i$，表示将 $a_{u_i}$ 修改为 $k_i$。

输出格式

共 $(q+1)$ 行，每行一个整数表示当前数列最小的幻数，如果没有幻数请输出 $-1$。

3
0 1 4
3
2 7
3 3
1 4

0
2
-1
4

提示

【数据范围】

注：本题只放部分数据，完整数据请左转 LOJ P2767 评测。