题目描述
题目译自 ROI 2017 Day 1 T2. Иллюзия сортировки
给一个数组 $a[1], a[2], \ldots, a[n]$，选择一个数 $b$，如果 $b$ 满足
$$(a[1] ⊕ b) ≤ (a[2] ⊕ b) ≤ . . . ≤ (a[n] ⊕ b)$$
则称 $b$ 是数组 $a$ 的幻数。此处 $⊕$ 表示按位异或。
该数组将会被先后修改 $q$ 次，我们每次只修改一个数。
第一次修改前以及每次修改后，请给出当前数组最小的幻数，如果当前数组不存在幻数请输出 $-1$。
输入格式
第一行有一个整数 $n$。
第二行有 $n$ 个整数，表示数组 $a$。
第三行有一个整数 $q$。
在接下来的 $q$ 行中，每行有两个整数 $p_i, v_i$，表示将 $a[p_i]$ 修改为 $v_i$。
输出格式
共 $(q+1)$ 行，每行一个整数，表示当前数组最小的幻数。
样例
input
3
0 1 4
3
2 7
3 3
1 4output
0
2
-1
4
数据范围与提示
| 子任务 | 分值 | $n$ | $q$ | $a[i], v_i$ |
|---|---|---|---|---|
| 1 | 30 | $1⩽n⩽500$ | $0⩽q⩽500$ | $0 ⩽ a[i], v_i ⩽ 2^9$ |
| 2 | 29 | $1⩽n⩽1000$ | $0⩽q⩽1000$ | $0 ⩽ a[i], v_i ⩽ 2^{30}$ |
| 3 | 21 | $1⩽n⩽10^5$ | $0⩽q⩽10^5$ | $0 ⩽ a[i], v_i ⩽ 2^{30}$ |
| 4 | 20 | $1⩽n⩽10^6$ | $0⩽q⩽10^6$ | $0 ⩽ a[i], v_i ⩽ 2^{30}$ |