В ряд находятся \(n\) кучек камней. В \(i\)-й кучке изначально \(h_i\) камней. Вы хотите изменить число камней в кучках, выполнив следующий процесс один раз:
- Вы идете по кучкам от \(3\)-й до \(n\)-й, в таком порядке.
- Пусть \(i\) — номер текущей кучки.
- Вы можете выбрать целое число \(d\) (\(0 \le 3 \cdot d \le h_i\)), переместить \(d\) камней из \(i\)-й кучки в \((i - 1)\)-ю кучку, и \(2 \cdot d\) камней из \(i\)-й кучки в \((i - 2)\)-ю.
- Таким образом, \(h_i\) уменьшается на \(3 \cdot d\), \(h_{i - 1}\) увеличивается на \(d\), и \(h_{i - 2}\) увеличивается на \(2 \cdot d\).
- Вы можете выбирать различные или одинаковые \(d\) для различных операций. Некоторые кучки могут стать пустыми, но они все еще считаются за кучки.
Какое наибольшее число камней в наименьшей кучке может получиться после завершения процесса?
Выходные данные
Для каждого набора входных данных выведите максимальное число камней, которое может содержать наименьшая по количеству камней кучка после завершения процесса.
Примечание
В первом примере изначально размеры кучек равны \([1, 2, 10, 100]\). Мы можем перемещать камни следующим образом.
- переместить \(3\) и \(6\) камней с \(3\)-й кучки на \(2\)-ю и \(1\)-ю кучки соответственно. Размеры кучек будут равны \([7, 5, 1, 100]\);
- Переместить \(6\) и \(12\) камней с последней кучки на \(3\)-ю и \(2\)-ю кучки соответственно. Размеры кучек будут равны \([7, 17, 7, 82]\).
Во втором наборе размер последней кучки равен \(1\) и мы не можем его увеличить.
В третьем наборе оптимально не перемещать никакие камни.
В четвертом примере можно достичь состояния, в котором размеры кучек равны \([3, 5, 3, 4, 3, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6
|
7
1
1
3
|