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

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