题目内容

塔子哥是一位珠宝设计师，他最近设计了一条独特的珍珠项链。

这条项链由$n$颗珍珠组成，每颗珍珠都有其独特的价值。

塔子哥想要将这条项链切割成两部分，以制作成一对手链。

为了使这对手链看起来协调，塔子哥决定将项链切割成两部分，使得左边部分珍珠的总价值乘以右边部分珍珠的总价值最小。

他希望你能帮他计算出这个最小值。

输入描述

第一行输入一个整数$n$，表示珍珠项链的长度。

第二行输入$n$个整数$a_1,a_2,…, a_n$，表示每颗珍珠的价值。

输出描述

输出一个整数，表示切割后两部分珍珠总价值的乘积的最小值。

样例1

输入

5
1 2 3 4 5

输出

14

说明

将项链在第一颗珍珠后切割,左边部分价值为$1$，右边部分价值为$14(2+3+4+5=14)$，

乘积为14，这是最小的可能值。

• $2≤n≤10^6$
• $-10^3 ≤a_i≤ 10^3$

样例2

输入

2 1 3 4

输出

16