Перси Джексон и боги Олимпа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед тем, как вся история с украденными молниями Зевса началась, Перси, конечно же, должен был как-то узнать о своем происхождении и вообще о богах Олимпа, а также о том, что древнегреческие боги и чудовища существуют в реальном мире.

Про богов Олимпа Перси впервые узнал из книги, подаренной ему еще совсем в детстве. В ней на одной из иллюстраций все $$$n$$$ богов были расположены в ряд, и снизу было подписано, что сила $$$i$$$-го бога равна $$$a_i$$$. Назовем диссонансом в этом ряду максимальную абсолютную разницу между силой соседних богов, то есть $$$$$$D = \max\limits_{i=1}^{n-1}(|a_i - a_{i+1}|) \text{.}$$$$$$

Сейчас, когда Перси поближе познакомился с богами и остальными существами, он стал уверен, что в книге была опечатка. Поскольку книга все-таки серьезная, опечатка могла быть только одна, и при этом Перси считает, что если ее исправить, то есть изменить какое-то одно $$$a_i$$$ на другое целое число, значение диссонанса $$$D$$$ станет минимально возможным.

Помогите Перси определить, какое $$$a_i$$$ надо исправить, чтобы добиться минимального значения диссонанса в ряду богов Олимпа.

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

В первой строке ввода дано единственное целое число $$$n$$$ — количество богов Олимпа на иллюстрации в книге ($$$2 \le n \le 5 \cdot 10^5$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — указанные в книге уровни силы богов ($$$1 \le a_i \le 10^9$$$).

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

Выведите через пробел три целых числа: $$$D_\mathrm{min}$$$, $$$i$$$ и $$$a_i^*$$$ — минимальное значение диссонанса, которого можно добиться, а также у какого по номеру бога надо изменить значение силы, и чему на самом деле его сила должна быть равна.

Если возможных вариантов ответа несколько, выведите любой из них. В частности, если $$$D_\mathrm{min}$$$ совпадает с исходным значением $$$D$$$, можете вывести любой $$$i$$$ и $$$a_i^* = a_i$$$, тогда можно считать, что опечатки в книге не было.

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

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

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
113$$$a_i \le 2$$$ для всех $$$i$$$полная
212$$$a_i \le 3$$$ для всех $$$i$$$1первая ошибка
317$$$n \le 100$$$, $$$a_i \le 100$$$ для всех $$$i$$$0первая ошибка
411$$$n \le 100$$$0, 3первая ошибка
514$$$n \le 10^4$$$, $$$a_i \le 100$$$ для всех $$$i$$$0, 3первая ошибка
615$$$n \le 2 \cdot 10^4$$$0, 3, 4, 5первая ошибка
718без дополнительных ограничений0 – 6первая ошибка

Примеры

Входные данные
5
4 1 3 5 4
Выходные данные
2 2 3
Входные данные
4
1 2 1 1
Выходные данные
0 2 1