Дано масив 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⋅(1+3)=12. Розглянемо інший підмасив a[1..2], елементи (a[1..2]) — [5,3]. Його довжина — 2, перший мінімум — 3, другий мінімум — 5. Виходить, що його ціна 2⋅(3+5)=16.
Зверніть увагу, що якщо мінімальне число трапляється більше одного разу, то воно все одно рахується кілька разів. Наприклад, якщо є підмасив [3,1,1], то його довжина — 3, перший мінімум — 1, другий мінімум — 1. Тобто його ціна — 3⋅(1+1)=6.
Ваше завдання — знайти максимальну ціну щодо всіх підмасивів довжини, як мінімум, два елементи. Тобто потрібно знайти максимальну ціну за всіма підмасивами a[l..r], де (1≤l<r≤n).
Перший рядок містить одне ціле число n (2≤n≤106).
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤109).
Виведіть одне ціле число — відповідь на задачу.
У першому прикладі максимум досяжний на підмасиві a[1..5], його довжина 5, мінімуми — 1 i 3, добуток (1+3)⋅5=20.
У другому прикладі максимум досяжний на підмасиві a[5..6], його довжина 2, мінімуми — 10 i 77, добуток (10+77)⋅2=174.
У третьому прикладі максимум досяжний на підмасиві a[2..3], його довжина 2, мінімуми — 2 i 3, добуток (2+3)⋅2=10.
(6 бали): 2≤n≤800
(7 бали): 2≤n≤5000
(10 балів): 2≤n≤20000
(24 балів): Усі тести згенеровано рандомно наступним чином: спершу визначається число n, що відбувається не рандомно, а потім для кожного ai (1≤i≤n ) присвоюється значення від 1 до 109 включно з однаковою ймовірністю для кожного значення. 2≤n≤105.
(17 балів): 2≤ai≤n
(36 балів): Без додаткових обмежень