Максимум функції

Limits: 2 sec., 256 MiB

Задано масив цілих чисел.

Потрібно знайти максимум функції $f(i, j) = a_i \cdot j + a_j \cdot i$.

Input

У першому рядку задано ціле число $n$ — розмір масиву.

У другому рядку задано $n$ цілих чисел $a_i$ — елементи масиву.

Output

У єдиному рядку виведіть ціле число — максимальне значення функції.

Constraints

12 тестів: $1 \le n \le 10^3$,

25 тестів: $1 \le n \le 10^6$,

$1 \le a_i \le 10^3$.

Samples