Цукерочки на олімпіаду

Обмеження: 2 сек., 256 МіБ

Перед сьогоднішньою олімпіадою Марічка зайшла в магазин солодощів «Рошан». Вона вірить, що цукерочки допоможуть їй краще й швидше розв’язувати задачі.

У магазині є \(n\) видів цукерочок. Солодкість цукерочок \(i\)-ого виду становить \(a_i\).

У Марічки є гроші лише на два види цукерочок, адже вона допомагає Алготестеру збирати на дрони для ЗСУ.

Марічка думає, що якщо вона їстиме на олімпіаді цукерочки спочатку \(i\)-ого, а потім \(j\)-ого виду, то їхня ефективність для розв’язування задач становитиме \((a_i + j) - (a_j + i)\). Зауважте, що порядок з’їдання важливий. Якщо їсти в іншому порядку — спершу цукерочки \(j\)-ого виду, а потім \(i\)-ого, то ефективність може відрізнятися.

Якої найбільшої ефективності може досягнути Марічка, придбавши цукерочки двох видів?

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість видів цукерочок.

У наступному рядку задано \(n\) цілих чисел \(a_i\) — солодкість цукерочок \(i\)-ого виду.

Вихідні дані

У єиному рядку виведіть найбільшу ефективність цукерочок.

Обмеження

\(2 \le n \le 4 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Оцінювання задачі складається з таких блоків:

1 бал — приклад з умови,

19 балів — \(n \le 1000\),

5 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 5 2 7 44	40

Примітки

У прикладі Марічка може вибрати \(i=5\) і \(j=3\). Тоді ефективність цукерочок становитиме \((a_5+3)-(a_3+5)=(44+3)-(2+5)=40\).