Цукерочки на олімпіаду
Обмеження: 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\).
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|