Добуток

Дано масив $a$ довжиною $n$. Ціна підмасиву — це добуток довжини підмасиву на суму двох найменших чисел.

Підмасив $a[l..r]$ — це частина масиву $a$, якщо брати до уваги лише числа, що знаходяться на позиціях від $l$ до $r$ включно.

Наприклад, нехай дано масив $[5,3,1,5,3]$. Розглянемо підмасив $a[\mathrm{2..4}]$, елементи ($a[\mathrm{2..4}]$) — $[3,1,5]$. Його довжина — $3$, перший мінімум — $1$, другий мінімум — $3$. Виходить, що його ціна — $3\cdot (1+3)=12$. Розглянемо інший підмасив $a[\mathrm{1..2}]$, елементи ($a[\mathrm{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\le l<r\le n$).

Вхідні дані

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

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

Вихідні дані

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

Приклади

Примітка

У першому прикладі максимум досяжний на підмасиві $a[\mathrm{1..5}]$, його довжина $5$, мінімуми — $1$ i $3$, добуток $(1+3)\cdot 5=20$.

У другому прикладі максимум досяжний на підмасиві $a[\mathrm{5..6}]$, його довжина $2$, мінімуми — $10$ i $77$, добуток $(10+77)\cdot 2=174$.

У третьому прикладі максимум досяжний на підмасиві $a[\mathrm{2..3}]$, його довжина $2$, мінімуми — $2$ i $3$, добуток $(2+3)\cdot 2=10$.

Оцінювання

1. ($6$ бали): $2\le n\le 800$

2. ($7$ бали): $2\le n\le 5000$

3. ($10$ балів): $2\le n\le 20000$

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$ балів): Без додаткових обмежень