### 问题描述 迪迦奥特曼，这位跨越宇宙的守护者，除了在战斗中展现出色的英勇和力量外，还有一个颇为奇特的兴趣 —— 他对石子情有独钟。 迪迦奥特曼从不仅仅将石子视为普通的地质材料，而是将它们看作一种富有哲学深度的存在。在他的眼中，每一块石子都是自然演化的产物，承载着地球的岁月和历史。他迷恋于石头表面的纹理、颜色以及它们在自然界中的形成过程。 现在有 $n$ 堆石子围成一个环，第 $i$ 堆有 $a_i$ 个石子，每次迪迦奥特曼可以选择相邻的 $2$ 堆石子，将这两堆石子合并，合并后的石子个数为两堆石子个数之和，合并的代价为两堆石子个数之积，迪迦奥特曼想知道将这 $n$ 堆石子合并成 $1$ 堆的最小代价。 以下给出两堆石子相邻的解释： > 假设现在有 $n$ 堆石子 $(n \geq 2)$ ，石子两堆石子 $i,j$ 是相邻的，当且仅当 $|i - j|=1$ 或 $|i-j|=n-1$。 ### 输入格式 第一行包含 $1$ 个正整数 $n$。 第二行有 $n$ 个正整数，第 $i$ 个表示权值 $a_i$。 ### 输出格式 输出共 $1$ 行，包含 $1$ 个整数，表示最终答案。 ### 样例输入 ```text 3 1 2 1 ``` ### 样例输出 ```text 5 ``` ### 评测数据规模 对于所有测评数据，$1 \leq n \leq 3\times 10^4，1 \leq a_i \leq 2 \times 10^5$。