题目描述

有 $n$ 个整数，其中第 $i$ 个整数为 $a_i$。求

$$\max \sum\limits_{i=l}^ra_i\times\sum\limits_{i=l}^ra_i $$

其中 $1\le l\le r \le n$。

输入

第一行一个正整数 $n$。 第二行 $n$ 个整数，其中第 $i$ 个整数为 $a_i$。

输出

一个整数，表示算式的最大值。

样例

4
1 4 -1 -5

36

数据范围

• $n\le 2\times10^3$
• $\left\vert a_i \right\vert \le 10^4$，其中 $i\in[1,n]$