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

Limits: 2 sec., 256 MiB

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

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

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

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

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

Input

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

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

Output

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

Constraints

$2 \le n \le 4 \cdot 10^5$,

$1 \le a_i \le 10^9$.

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

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

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 5 2 7 44	40

Notes

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