CF1716E.Swap and Maximum Block

You are given an array of length $2^n$. The elements of the array are numbered from $1$ to $2^n$.

You have to process $q$ queries to this array. In the $i$-th query, you will be given an integer $k$ ($0 \le k \le n-1$). To process the query, you should do the following:

• for every $i \in [1, 2^n-2^k]$ in ascending order, do the following: if the $i$-th element was already swapped with some other element during this query, skip it; otherwise, swap $a_i$ and $a_{i+2^k}$;
• after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment).

For example, if the array $a$ is $[-3, 5, -3, 2, 8, -20, 6, -1]$, and $k = 1$, the query is processed as follows:

• the $1$-st element wasn't swapped yet, so we swap it with the $3$-rd element;
• the $2$-nd element wasn't swapped yet, so we swap it with the $4$-th element;
• the $3$-rd element was swapped already;
• the $4$-th element was swapped already;
• the $5$-th element wasn't swapped yet, so we swap it with the $7$-th element;
• the $6$-th element wasn't swapped yet, so we swap it with the $8$-th element.

So, the array becomes $[-3, 2, -3, 5, 6, -1, 8, -20]$. The subsegment with the maximum sum is $[5, 6, -1, 8]$, and the answer to the query is $18$.

Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.

给你一个长度为 $2^n$ 的数组。数组元素的编号从 $1$ 到 $2^n$。

你需要处理 $q$ 个对该数组的查询。在第 $i$ 个查询中，你将得到一个整数 $k$（$0 \le k \le n-1$）。为了处理该查询，你需要执行以下操作：

• 对每个按升序排列的 $i \in [1, 2^n-2^k]$，执行如下操作：若第 $i$ 个元素在本次查询中已被与其他元素交换过，则跳过；否则，交换 $a_i$ 与 $a_{i+2^k}$；
• 然后，输出该数组所有连续子段（包括空子段）的最大和。

例如，若数组 $a$ 为 $[-3, 5, -3, 2, 8, -20, 6, -1]$，且 $k = 1$，则该查询的处理过程如下：

• 第 $1$ 个元素尚未被交换，因此将其与第 $3$ 个元素交换；
• 第 $2$ 个元素尚未被交换，因此将其与第 $4$ 个元素交换；
• 第 $3$ 个元素已被交换过；
• 第 $4$ 个元素已被交换过；
• 第 $5$ 个元素尚未被交换，因此将其与第 $7$ 个元素交换；
• 第 $6$ 个元素尚未被交换，因此将其与第 $8$ 个元素交换。

于是，数组变为 $[-3, 2, -3, 5, 6, -1, 8, -20]$。具有最大和的连续子段为 $[5, 6, -1, 8]$，该查询的答案为 $18$。

注意：这些查询会实际修改数组，即执行完一个查询后，数组不会恢复至原始状态，下一个查询将在已修改的数组上进行。

The first line contains one integer $n$ ($1 \le n \le 18$).

The second line contains $2^n$ integers $a_1, a_2, \dots, a_{2^n}$ ($-10^9 \le a_i \le 10^9$).

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

Then $q$ lines follow, the $i$-th of them contains one integer $k$ ($0 \le k \le n-1$) describing the $i$-th query.

第一行包含一个整数 $n$（$1 \le n \le 18$）。

第二行包含 $2^n$ 个整数 $a_1, a_2, \dots, a_{2^n}$（$-10^9 \le a_i \le 10^9$）。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。

接下来有 $q$ 行，其中第 $i$ 行包含一个整数 $k$（$0 \le k \le n-1$），表示第 $i$ 个查询。

For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

对于每个查询，输出一个整数——即处理完该查询后，数组所有连续子段（包括空子段）的最大和。

Transformation of the array in the example: $[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]$.

示例中的数组变换：$[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]$。