4. Награждение участников олимпиады
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
 —Мы все третье место заняли: и я, и Мишка, и Толька, и Кимка, все-все. Вовка — первое, рыжий лягушонок — второе, а мы, остальные восемнадцать человек, мы заняли третье. Так инструктор сказал!
Виктор Драгунский, «Третье место в стиле баттерфляй».

Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли $$$a_1$$$ участников, второе место $$$a_2$$$ участников, $$$\ldots$$$, заключительное $$$n$$$-е место заняли $$$a_n$$$ участников.

Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в $$$P$$$ денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:

1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;

2) Всем участникам, занявшим заключительное $$$n$$$-е место достанутся призы стоимостью в 1 денежную единицу;

3) Разница $$$d$$$ между призом участника на $$$i$$$-м месте и призом участника на $$$i + 1$$$-м месте должна быть одинакова для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$, в том числе, может быть и так, что $$$d = 0$$$, то есть все участники могут получить одинаковые призы, независимо от занятого ими места.

Необходимо определить, какую максимальную разницу $$$d$$$ жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы $$$P$$$.

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

В первой строке входных данных содержится одно натуральное число $$$n$$$ — количество различных мест, которые заняли участники олимпиады ($$$2 \leqslant n \leqslant 10^5$$$). В следующих $$$n$$$ строках, по одному в строке, находятся натуральные числа $$$a_i$$$ — количество участников, занявших $$$i$$$-е место ($$$i$$$ от $$$1$$$ до $$$n$$$). Общее количество участников $$$a_1 + a_2 + \ldots + a_n$$$ не превосходит $$$10^{18}$$$, любое $$$a_i$$$ не менее 1. В последней строке находится натуральное число $$$P$$$ — сумма, заложенная в смете на призы ($$$P \leqslant 10^{18}$$$). Гарантируется, что $$$P \geqslant a_1 + a_2 + \ldots + a_n$$$, то есть для каждого участника можно купить приз стоимостью как минимум в одну денежную единицу.

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

Выведите одно неотрицательное целое число — максимальную разницу $$$d$$$, которую можно запланировать, не выходя за пределы суммы $$$P$$$.

Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться $$$64$$$-битный тип данных, например, long long в C++, int64 в Pascal, long в Java.

Система оценки

Решения, правильно работающие для случаев, в которых $$$P / n$$$ не превосходит $$$10^6$$$, получат не менее 60 баллов.

Пример
Входные данные
5
2
1
3
4
2
100
Выходные данные
4
Примечание

В примере участники распределились следующим образом:

1 место — 2 участника,

2 место — 1 участник,

3 место — 3 участника,

4 место — 4 участника,

5 место — 2 участника.

Если заложить разницу между призами в 4 денежных единицы, то распределение стоимостей призов будет следующим:

5 место — 2 приза по 1 денежной единице,

4 место — 4 приза по 5 денежных единиц,

3 место — 3 приза по 9 денежных единиц,

2 место — 1 приз по 13 денежных единиц,

1 место — 2 приза по 17 денежных единиц.

Суммарно на призы будет потрачено 2 * 1 + 4 * 5 + 3 * 9 + 1 * 13 + 2 * 17 = 96 денежных единиц, что укладывается в смету в 100 денежных единиц.

Если же заложить разницу между призами в 5 денежных единиц, то потребуется 2 * 1 + 4 * 6 + 3 * 11 + 1 * 16 + 2 * 21 = 117 денежных единиц, что превышает сумму, указанную в смете.