说明

给定一个长度为 $2^N - 1$ 的整数序列 $B = (B_1, B_2, \ldots, B_{2^N - 1})$，定义 $f(B)$ 如下：

• $f(B)$ 是使以下条件成立所需的最少操作次数：
  • 操作：选择一个整数 $i$，满足 $1 \leq i \leq 2^N - 1$，并将 $B_i$ 增加 $1$ 或减少 $1$。
  • 条件：对于所有满足 $1 \leq i \leq 2^{N-1} - 1$ 的 $i$，条件 $B_i = B_{2i} + B_{2i+1}$ 应被满足。

给定一个长度为 $2^N - 1$ 的序列 $A = (A_1, A_2, \ldots, A_{2^N - 1})$。

处理 $Q$ 个查询。对于每个查询 $i$（其中 $1 \leq i \leq Q$）：

• 给定整数 $x_i$ 和 $v_i$，将 $A_{x_i}$ 更新为 $v_i$，然后输出 $f(A)$。

输入格式

输入以如下格式给出：

$$\begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_{2^N - 1} \\ &Q \\ &x_1 \ v_1 \\ &x_2 \ v_2 \\ &\vdots \\ &x_Q \ v_Q \end{aligned}$$

• $2 \leq N \leq 18$
• $1 \leq Q \leq 100,000$
• $-10^9 \leq A_i \leq 10^9$
• $1 \leq x_i \leq 2^N - 1$
• $-10^9 \leq v_i \leq 10^9$
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。在第 $i$ 行输出第 $i$ 个查询的答案。

3
2 3 0 1 -5 2 1
5
3 1
5 3
6 -1
5 1
1 0

9
5
3
2
4