题目描述

Bitek 有 $n$ 块木板，第 $i$ 块长度为 $d_i$。他必须使用所有木板围成一个矩形羊圈。

木板必须首尾相接，并且已经固定了循环顺序：对于 $1\le i<n$，木板 $i$ 必须与木板 $i+1$ 相接，木板 $n$ 还必须与木板 $1$ 相接。

也就是说，只能决定哪些相邻木板共同组成矩形的四条边，而不能改变木板的循环顺序。每条矩形边可以由若干连续木板组成。

求能够围出的最大矩形面积。若无法围成矩形，输出 $0$。

输入格式

第一行一个整数 $n$，$4\le n\le10^6$。

接下来 $n$ 行，第 $i$ 行一个整数 $d_i$，满足 $1\le d_i\le10^9$。

保证 $\sum d_i\le10^9$。

部分测试（共 40 分）满足 $n\le10^4$。

输出格式

输出一个整数，表示最大可能面积；若无解输出 $0$。

样例输入

8
1
5
1
3
2
3
2
1

样例输出

20