Задача D. Скорость воробьёв

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Юный орнитолог Вася решил узнать, насколько быстро способны летать воробьи. Для этого он нашёл ряд из N кустов, растущих вдоль одно прямой на расстоянии ровно 1 метр друг от друга.

Воробьи часто сидят на кустах и перелетают с одного на другой. Вася сделал две фотографии деревьев с воробьями с интервалом ровно в 1 секунду. К сожалению, все воробьи выглядят одинаково, и Вася не может по фотографии определить, какой воробей куда перелетел.

Однако оказалось, что на первой фотографии на каждом из кустов сидит ровно по одному воробью, а на второй — на i-м кусте сидят ai воробьёв. (a1 + a2 + … + aN = N).

Вам необходимо написать программу, которая определит по этим данным минимально возможную скорость, с которой способны летать воробьи. Предполагается, что на вторую фотографию попали те же самые воробьи, что и на первую.

Формат входного файла

Во входном файле содержится число N, за которым следует N целых чисел ai.

Формат выходного файла

В выходном файле должно содержаться единственное целое число — минимальная скорость воробья в м/с.

Ограничения

1 ≤ N ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 1
0
2
5
0 2 3 0 0
2

0.034s 0.007s 15