[Solution] Swap and Maximum Block Codeforces Solution

E. Swap and Maximum Block

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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

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

• for every i∈[1,2n−2k]$i\in [1,2^n-2^k]$ in ascending order, do the following: if the i$i$-th element was already swapped with some other element during this query, skip it; otherwise, swap ai$a_i$ and ai+2k$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$a$ is [−3,5,−3,2,8,−20,6,−1]$[-3,5,-3,2,8,-20,6,-1]$,

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 and k=1$k=1$, the query is processed as follows:

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

So, the array becomes [−3,2,−3,5,6,−1,8,−20]$[-3,2,-3,5,6,-1,8,-20]$. The subsegment with the maximum sum is [5,6,−1,8]$[5,6,-1,8]$, and the answer to the query is 18$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.

Input

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

The second line contains 2n$2^n$ integers a1,a2,…,a2n$a_1,a_2,\dots ,a_{2^n}$ (−109≤ai≤109$-{10}^9\le a_i\le {10}^9$).

The third line contains one integer q$q$ (1≤q≤2⋅105$1\le q\le 2\cdot {10}^5$).

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

Output

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