Задача D. Пересадка

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

Условие

На автобусную остановку каждую минуту приходит ровно один автобус. Имеется расписание на N минут, в котором для каждой минуты указан номер маршрута автобуса, приходящего в эту минуту.

Требуется определить максимальное время, которое пассажир может затратить на пересадку с одного маршрута на другой, то есть максимальный интервал (в минутах) между прибытиями автобусов двух разных маршрутов, в течение которого других автобусов этих маршрутов на остановке не будет.

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

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

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

Выходной файл должен содержать единственно число — длину максимального интервала в минутах.

Ограничения

2 ≤ N ≤ 105, 1 ≤ ai ≤ 109.

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

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

0.035s 0.007s 15