题目描述

Given an integer sequence $B = (B_1, B_2, \ldots, B_{2^N - 1})$ of length $2^N - 1$, define $f(B)$ as follows:

• $f(B)$ is the minimum number of operations required to make the following condition true:
  • Operation: Choose one integer $i$ such that $1 \leq i \leq 2^N - 1$, and either increase $B_i$ by $1$ or decrease $B_i$ by $1$.
  • Condition: For all $i$ where $1 \leq i \leq 2^{N-1} - 1$, the condition $B_i = B_{2i} + B_{2i+1}$ should be satisfied.

You are given a sequence $A = (A_1, A_2, \ldots, A_{2^N - 1})$ of length $2^N - 1$.

Process $Q$ queries. For each query $i$ (where $1 \leq i \leq Q$):

• Given integers $x_i$ and $v_i$, update $A_{x_i}$ to $v_i$ and then output $f(A)$.

输入格式

The input is given in the following format:

$$\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$
• All input values are integers.

输出格式

Output $Q$ lines. On the $i$-th line, output the answer for the $i$-th query.

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

9
5
3
2
4