3. Арт-объект
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Арт-объект представляет собой $$$n$$$ колонн высотой $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ сантиметров. Критики считают, что арт-объект станет выглядеть лучше, если высоты колонн будут идти по неубыванию, то есть высота каждой колонны должна быть не меньше высоты предыдущей колонны ($$$a_i\ge a_{i-1}$$$ для всех $$$i\ge2$$$).

Поскольку порядок колонн нельзя менять (это разрушит замысел автора), колонны можно расположить на лестнице, высота ступеньки которой равна $$$d$$$. При этом на каждой ступеньке будет стоять одна колонна, а первая колонна должна стоять на первой ступеньке. Тогда высота первой колонны $$$a_1$$$ увеличится на $$$d$$$, высота второй колонны $$$a_2$$$ увеличится на $$$2d$$$, значение $$$a_3$$$ увеличится на $$$3d$$$ и так далее.

Чтобы арт-объект не стал слишком громоздким, нужно найти минимальную подходящую высоту ступеньки $$$d$$$, при которой высоты колонн станут неубывающими.

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

Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество колонн.

В следующих $$$n$$$ строках записаны высоты колонн $$$a_i$$$, $$$1\le a_i \le 10^9$$$.

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

Программа должна вывести минимальную подходящую высоту ступеньки $$$d$$$. Если высоты колонн уже неубывают, необходимо вывести число 0.

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

Решения, правильно работающие при $$$n \le 2$$$, будут оцениваться в $$$20$$$ баллов.

Решения, правильно работающие при $$$a_i \le 10$$$, будут оцениваться в $$$30$$$ баллов.

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

В первом примере высоты колонн равны $$$1, 5, 2, 7, 5$$$. Если использовать лестницу со ступенькой $$$d=3$$$, то высоты колонн станут $$$4, 11, 11, 19, 20$$$. Если взять ступеньку $$$d=2$$$, то получатся высоты $$$3, 9, 8, 15, 15$$$, и тогда колонна номер 2 будет выше колонны номер 3.