Перед тем, как вся история с украденными молниями Зевса началась, Перси, конечно же, должен был как-то узнать о своем происхождении и вообще о богах Олимпа, а также о том, что древнегреческие боги и чудовища существуют в реальном мире.
Про богов Олимпа Перси впервые узнал из книги, подаренной ему еще совсем в детстве. В ней на одной из иллюстраций все $$$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 | – | примеры из условия | полная | |
1 | 13 | $$$a_i \le 2$$$ для всех $$$i$$$ | полная | |
2 | 12 | $$$a_i \le 3$$$ для всех $$$i$$$ | 1 | первая ошибка |
3 | 17 | $$$n \le 100$$$, $$$a_i \le 100$$$ для всех $$$i$$$ | 0 | первая ошибка |
4 | 11 | $$$n \le 100$$$ | 0, 3 | первая ошибка |
5 | 14 | $$$n \le 10^4$$$, $$$a_i \le 100$$$ для всех $$$i$$$ | 0, 3 | первая ошибка |
6 | 15 | $$$n \le 2 \cdot 10^4$$$ | 0, 3, 4, 5 | первая ошибка |
7 | 18 | без дополнительных ограничений | 0 – 6 | первая ошибка |
54 1 3 5 4
2 2 3
41 2 1 1
0 2 1