Долгое путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На астероиде в сторону Земли летят $$$n$$$ симбиотов. Чтобы пережить долгий перелет, симбиоты расположились в самой благоприятной для космических полётов формации — по кругу. Известно, что $$$i$$$-й из симбиотов в порядке по часовой стрелке имеет массу $$$a_i$$$. Не чаще, чем раз в год, один из еще живых симбиотов жертвует собой ради выживания других. Если $$$i$$$-й симбиот жертвует собой, его соседи, находящиеся на местах $$$(i + 1) \bmod n$$$ и $$$(i - 1) \bmod n$$$, ассимилируют по его половине (округленной вниз до целого, если его масса была нечетна), прибавляя ассимилированную массу к своей. На месте пожертвовавшего собой симбиота остается пустое место, которое никто не занимает. Если с какой-то стороны от жертвующего собой симбиота уже находится пустое место, его соответствующая половина никем не ассимилируется и просто исчезает в космосе.

В некоторые года симбиоты спокойно продолжают свой перелет и никто собой не жертвует.

Карлтон Дрейк из «Фонда жизни» собирался отправить к этому астероиду ракету, но ему не было известно, сколько точно лет она будет лететь до астероида. Поэтому он рассчитал $$$q$$$ возможных наиболее вероятных времен полета $$$t_i$$$ и захотел для каждого из них узнать, симбиот с каким наибольшим весом может его ждать на астероиде.

Разумеется, он в свое время смог посчитать интересующие его величины. А можете ли их восстановить вы?

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

В первой строке ввода дано целое число $$$n$$$ — изначальное количество симбиотов на астероиде ($$$3 \leqslant n \leqslant 2 \cdot 10^4$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — изначальные массы симбиотов ($$$1 \leqslant a_i \leqslant 10^9$$$).

В третьей строке ввода дано целое число $$$q$$$ — количество запросов, ответы на которых интересовали Дрейка ($$$1 \leqslant m \leqslant 2 \cdot 10^5$$$).

В следующей строке через пробел перечислены сами запросы $$$t_i$$$ — ожидаемые времена полета, для которых требуется найти максимальную возможную массу симбиота на астероиде спустя ровно столько времени ($$$1 \leqslant t_i \leqslant n$$$).

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

Выведите $$$q$$$ строк, по строке на каждый запрос. В $$$i$$$-й строке выведите максимальную достижимую за $$$t_i$$$ лет каким-либо симбиотом массу.

Примеры

Входные данные
3
1 4 7
2
1 2
Выходные данные
9
10
Входные данные
5
1 3 5 7 9
3
1 2 5
Выходные данные
12
13
15
Входные данные
4
2 4 8 16
4
1 2 3 4
Выходные данные
20
21
23
23