E. Обмен и максимальный отрезок
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив длины $$$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$$$.

Обратите внимание, что запросы изменяют массив, т. е. после выполнения запроса массив не возвращается в изначальное состояние, и следующий запрос будет применен к измененному массиву.

Входные данные

В первой строке записано одно целое число $$$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$$$-й запрос.

Выходные данные

На каждый запрос выведите одно целое число — наибольшую сумму среди всех непрерывных подотрезков массива (включая пустой подотрезок) после обработки запроса.

Пример
Входные данные
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
Выходные данные
18
8
13
Примечание

Преобразование массива в примере: $$$[-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]$$$.