题目：

Description

给定正整数n和正整数数组A_i(1<=i<=n)

现有n堆石子排成一列，第i堆石子有A_i个，其中对于任一正整数i(i<n)，

第i堆石子与第i+1堆石子相邻。每次将两堆石子合并成一堆，新堆的石子数是原来两堆石子数之和，代价是原来两堆石子数之积，

求合并n-1次将n堆石子合并成一堆的代价和最小是多少。

Format Input 第一行，一个正整数n。

第二行，n个正整数，第i个正整数表示A_i，相邻两个数之间有一个空格隔开。

N<=3e5

A_i<=2e5

Output

仅一行，一个正整数，表示答案

Samples

输入数据 1

3 1 2 3

输出数据

1 11

Hint

小心数据范围

（另外，本人是小白（QAQ），能否只把思路告诉我）