1803: Добуток
Перегляд у форматі PDFДано масив ~a~ довжиною ~n~. Ціна підмасиву --- це добуток довжини підмасиву на суму двох найменших чисел.
Підмасив ~a[l..r]~ --- це частина масиву ~a~, якщо брати до уваги лише числа, що знаходяться на позиціях від ~l~ до ~r~ включно.
Наприклад, нехай дано масив ~[5, 3, 1, 5, 3]~. Розглянемо підмасив ~a[2..4]~, елементи (~a[2..4]~) --- ~[3, 1, 5]~. Його довжина --- ~3~, перший мінімум --- ~1~, другий мінімум --- ~3~. Виходить, що його ціна --- ~3 \cdot (1 + 3) = 12~. Розглянемо інший підмасив ~a[1..2]~, елементи (~a[1..2]~) --- ~[5, 3]~. Його довжина --- ~2~, перший мінімум --- ~3~, другий мінімум --- ~5~. Виходить, що його ціна ~2 \cdot (3 + 5) = 16~.
Зверніть увагу, що якщо мінімальне число трапляється більше одного разу, то воно все одно рахується кілька разів. Наприклад, якщо є підмасив ~[3, 1, 1]~, то його довжина --- ~3~, перший мінімум --- ~1~, другий мінімум --- ~1~. Тобто його ціна --- ~3 \cdot (1 + 1) = 6~.
Ваше завдання --- знайти максимальну ціну щодо всіх підмасивів довжини, як мінімум, два елементи. Тобто потрібно знайти максимальну ціну за всіма підмасивами ~a[l..r]~, де (~1 \leq l < r \leq n~).
Оцінювання
- (~6~ бали): ~2 \le n \le 800~
- (~7~ бали): ~2 \le n \le 5\,000~
- (~10~ балів): ~2 \le n \le 20\,000~
- (~24~ балів): Усі тести згенеровано рандомно наступним чином: спершу визначається число ~n~, що відбувається не рандомно, а потім для кожного ~a_i~ (~1 \le i \le n~ ) присвоюється значення від ~1~ до ~10^9~ включно з однаковою ймовірністю для кожного значення. ~2 \le n \le 10^5~.
- (~17~ балів): ~2 \le a_i \le \sqrt{n}~
- (~36~ балів): Без додаткових обмежень
Формат вхідних даних
Перший рядок містить одне ціле число ~n~ ~(2 \le n \le 10^6)~.
Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.
Формат вихідних даних
Виведіть одне ціле число --- відповідь на задачу.
Примітка
У першому прикладі максимум досяжний на підмасиві ~a[1..5]~, його довжина ~5~, мінімуми --- ~1~ i ~3~, добуток ~(1+3) \cdot 5 = 20~.
У другому прикладі максимум досяжний на підмасиві ~a[5..6]~, його довжина ~2~, мінімуми --- ~10~ i ~77~, добуток ~(10+77) \cdot 2=174~.
У третьому прикладі максимум досяжний на підмасиві ~a[2..3]~, його довжина ~2~, мінімуми --- ~2~ i ~3~, добуток ~(2+3) \cdot 2=10~.
Приклад вхідних даних
5
5 3 1 5 3
Приклад вихідних даних
20
Приклад вхідних даних
7
1 1 3 5 10 77 5
Приклад вихідних даних
174
Приклад вхідних даних
3
1 2 3
Приклад вихідних даних
10
Коментарі
Damn, на мові С, код зі складністю NlogN, при N <= 10^6 виконується більше 3х секунд...
Проблема малої потужності сервера, авторський розвʼязок у нас помістився у 2.5с (на офіційних змаганнях виділялося 2с) - + 1 с.