Cho một dãy số nguyên gồm \(N\) phần tử. Hãy chia dãy thành hai phần không rỗng: phần trái và phần phải (giữ nguyên thứ tự ban đầu). Gọi \(S1\) là tổng các phần tử của phần trái, \(S2\) là tổng các phần tử của phần phải. Hãy tìm cách chia sao cho tích \(S1 \cdot S2\) là lớn nhất.

Input

• Dòng 1 chứa số nguyên \(N\) (\(2 \leq N \leq 10^5\)).
• Dòng 2 chứa \(N\) số nguyên \(A_i\) (\(1 \leq A_i \leq 10^6\)).

Output

• In ra một số nguyên là giá trị lớn nhất của \(S1 \cdot S2\).

Example

4
1 2 3 4

24