Цукерочки на олімпіаду
Limits: 2 sec., 256 MiB
Перед сьогоднішньою олімпіадою Марічка зайшла в магазин солодощів «Рошан». Вона вірить, що цукерочки допоможуть їй краще й швидше розв’язувати задачі.
У магазині є n видів цукерочок. Солодкість цукерочок i-ого виду становить ai.
У Марічки є гроші лише на два види цукерочок, адже вона допомагає Алготестеру збирати на дрони для ЗСУ.
Марічка думає, що якщо вона їстиме на олімпіаді цукерочки спочатку i-ого, а потім j-ого виду, то їхня ефективність для розв’язування задач становитиме (ai+j)−(aj+i). Зауважте, що порядок з’їдання важливий. Якщо їсти в іншому порядку — спершу цукерочки j-ого виду, а потім i-ого, то ефективність може відрізнятися.
Якої найбільшої ефективності може досягнути Марічка, придбавши цукерочки двох видів?
Input
У першому рядку задано ціле число n — кількість видів цукерочок.
У наступному рядку задано n цілих чисел ai — солодкість цукерочок i-ого виду.
Output
У єиному рядку виведіть найбільшу ефективність цукерочок.
Constraints
2≤n≤4⋅105,
1≤ai≤109.
Оцінювання задачі складається з таких блоків:
1 бал — приклад з умови,
19 балів — n≤1000,
5 балів — без додаткових обмежень.
Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.
Samples
Input (stdin) | Output (stdout) |
---|---|
5 4 5 2 7 44 | 40 |
Notes
У прикладі Марічка може вибрати i=5 і j=3. Тоді ефективність цукерочок становитиме (a5+3)−(a3+5)=(44+3)−(2+5)=40.