#GYM104664B. Noodle Tug of War

Noodle Tug of War

Description

In the spirited Noodle Tug of War event, a lively gathering of noodle enthusiasts takes place, where participants engage in a thrilling match, pulling on a long, stretchy noodle. The noodle represents the central element of this exciting event, symbolizing the unity and elation that noodles bring to people of all backgrounds. The entertainment score of the event is a crucial measure of the event's liveliness and vigor.

This year, $N$ ($1 \leq N \leq 10^5$) noodle enthusiasts are participating in this event. Each enthusiast has some strength score, where the $i$-th participant has a strength score $1 \leq \text{Strength}[i] \leq 10^4$.

The entertainment score of the event is determined by the product of the sum of strengths on the left and right sides of the noodle at the chosen splitting point. As the event organizer, you would like to maximize the event's entertainment score by splitting the noodle enthusiasts into two groups at a single index.

Given the number $N$ of participants and each participant's strength score, find the maximum value of $ \left(\sum_{i=1}^{k} \text{Strength}[i]\right) \times \left(\sum_{j=k+1}^{N} \text{Strength}[j]\right) $ for any valid index $k$ (1-indexed).

Note that teams of size $N = 1$ are possible. In this case, there will be one team with a single participant with some strength $x$ and another team has no members. This event is quite uninteresting, so the score is $x \cdot 0 = 0$.

The first line contains a single integer, $N$ ($1 \leq N \leq 10^5$): the number of noodle enthusiasts participating in the Noodle Tug of War.

The next line contains $N$ space-separated integers ($1 \leq \text{Strength}[i] \leq 10^4$): the strength of each noodle enthusiast.

Output a single integer, the maximum possible entertainment score.

Input

The first line contains a single integer, $N$ ($1 \leq N \leq 10^5$): the number of noodle enthusiasts participating in the Noodle Tug of War.

The next line contains $N$ space-separated integers ($1 \leq \text{Strength}[i] \leq 10^4$): the strength of each noodle enthusiast.

Output

Output a single integer, the maximum possible entertainment score.

5
1 2 3 4 5
4
3 2 5 1
54
30

Note

In the first example, we have the solution $(1 + 2 + 3)(4 + 5) = 54$

In the second example, we have the solution $(3 + 2)(5 + 1) = 30$