Hide

Inquiry I

The Bureau for Artificial Problems in Competitions wants you to solve the following problem: Given $n$ positive integers $a_1, \dots , a_ n$, what is the maximal value of

$\left(a_1^2 + \dots + a_ k^2\right) \cdot \left(a_{k+1} + \dots + a_ n\right)?$

Input

• A single line containing an integer $2\leq n\leq 10^6$.

• Then follow $n$ lines, the $i$th of which contains the integer $1 \leq a_ i \leq 100$.

Output

Output the maximal value of the given expression.

Sample Input 1 Sample Output 1
5
2
1
4
3
5

168

Sample Input 2 Sample Output 2
2
1
1

1

Sample Input 3 Sample Output 3
10
8
5
10
9
1
4
12
6
3
13

10530

CPU Time limit 9 seconds
Memory limit 1024 MB
Difficulty 2.4easy
Statistics Show