В один из дней преподаватели «Т-поколения» решили приучить школьников к дисциплине, поэтому поставили их в ряд. Вам известно, что всего есть \(n\) школьников, у \(i\)-го по порядку школьника рост равен \(a_i\).
Школьникам комфортно, если для каждого \(i\) от \(1\) до \(n - 1\) выполняется следующее условие: \(a_i \cdot 2 \ge a_{i + 1}\). Изначально школьникам комфортно.
Преподавателям не нравится то, что максимальный рост в ряду слишком маленький, поэтому они хотят накормить школьников пиццей. Если школьник съест одну пиццу, то его рост увеличится на \(1\). Одну пиццу может съесть только один школьник, но каждый школьник может съесть неограниченное количество пицц. Важно, чтобы после того как все школьники съели свои пиццы, школьникам было комфортно.
У преподавателей есть \(q\) вариантов того, сколько пицц они закажут. Для каждого варианта \(k_i\) ответьте на вопрос: какой максимальный рост \(\max(a_1, a_2, \ldots, a_n)\) можно получить, если школьники съедят не более \(k_i\) пицц.
Выходные данные
Для каждого набора входных данных для каждого варианта того, сколько максимум пицц могут съесть школьники, выведите максимальное значение \(\max(a_1, a_2, \ldots, a_n)\), которое можно получить, чтобы школьникам было комфортно.
Примечание
В первом запросе первого набора входных данных можно сначала дать \(3\) пиццы первому школьнику, а потом второму школьнику \(6\) пицц, тогда итоговый массив станет \([13, 26]\) (школьникам комфортно, так как \(13 \cdot 2 \ge 26\)), максимальный элемент в нем равен \(26\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1
10 20
10
6 7
3 1 2 4 5 6
1
2
4
8
16
32
64
10 4
1 2 4 8 16 32 64 128 256 512
10
100
1000
10000
|
26
7 8 10 12 19 35 67
513 560 1011 10001
|