Добуток
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Дано масив $$$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$$$).

Вхідні дані

Перший рядок містить одне ціле число $$$n$$$ $$$(2 \le n \le 10^6)$$$.

Другий рядок містить $$$n$$$ цілих чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Система оцінки

  1. ($$$6$$$ бали): $$$2 \le n \le 800$$$
  2. ($$$7$$$ бали): $$$2 \le n \le 5\,000$$$
  3. ($$$10$$$ балів): $$$2 \le n \le 20\,000$$$
  4. ($$$24$$$ балів): Усі тести згенеровано рандомно наступним чином: спершу визначається число $$$n$$$, що відбувається не рандомно, а потім для кожного $$$a_i$$$ ($$$1 \le i \le n$$$ ) присвоюється значення від $$$1$$$ до $$$10^9$$$ включно з однаковою ймовірністю для кожного значення. $$$2 \le n \le 10^5$$$.
  5. ($$$17$$$ балів): $$$2 \le a_i \le \sqrt{n}$$$
  6. ($$$36$$$ балів): Без додаткових обмежень

Приклади

Вхідні дані
5
5 3 1 5 3
Вихідні дані
20
Вхідні дані
7
1 1 3 5 10 77 5
Вихідні дані
174
Вхідні дані
3
1 2 3
Вихідні дані
10

Пояснення

У першому прикладі максимум досяжний на підмасиві $$$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$$$.