## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${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 \left[1,{2}^{n}-{2}^{k}\right]$ 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 $\left[-3,5,-3,2,8,-20,6,-1\right]$,

Solution Click Below:-  👉

👇👇👇👇👇

occupied

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 $\left[-3,2,-3,5,6,-1,8,-20\right]$. The subsegment with the maximum sum is $\left[5,6,-1,8\right]$, 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.

Input

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.

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.