| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 9 | 4 | 2 | 50.000% |
На астероиде в сторону Земли летят $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