Дано масив $$$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)$$$.
Виведіть одне ціле число — відповідь на задачу.
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$$$.