Добуток#11375

Добуток

2 секунди

256 мегабайтів

Дуже складна

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

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

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

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

Оцінювання

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