Добуток#191

Добуток

2 секунди
256 мегабайтів
Складна

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

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

Наприклад, нехай дано масив [5, 3, 1, 5, 3]. Розглянемо підмасив , елементи () — [3, 1, 5]. Його довжина — , перший мінімум — , другий мінімум — . Виходить, що його ціна — 3 \cdot (1 + 3) = 12. Розглянемо інший підмасив , елементи () — . Його довжина — , перший мінімум — , другий мінімум — . Виходить, що його ціна 2 \cdot (3 + 5) = 16.

Зверніть увагу, що якщо мінімальне число трапляється більше одного разу, то воно все одно рахується кілька разів. Наприклад, якщо є підмасив [3, 1, 1], то його довжина — , перший мінімум — , другий мінімум — . Тобто його ціна — 3 \cdot (1 + 1) = 6.

Ваше завдання — знайти максимальну ціну щодо всіх підмасивів довжини, як мінімум, два елементи. Тобто потрібно знайти максимальну ціну за всіма підмасивами , де (1 \leq l < r \leq n).

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

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

У другому прикладі максимум досяжний на підмасиві , його довжина , мінімуми — i , добуток (10+77) \cdot 2=174.

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

Оцінювання

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

  2. ( бали): 2 \le n \le 5\,000

  3. ( балів): 2 \le n \le 20\,000

  4. ( балів): Усі тести згенеровано рандомно наступним чином: спершу визначається число , що відбувається не рандомно, а потім для кожного a_i (1 \le i \le n ) присвоюється значення від до 10^9 включно з однаковою ймовірністю для кожного значення. 2 \le n \le 10^5.

  5. ( балів): 2 \le a_i \le \sqrt{n}

  6. ( балів): Без додаткових обмежень