You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $1,2,\dots,n$ 的排列 $p_1,p_2,\dots,p_n$。

构造一个 $n$ 个点的完全无向图，节点编号分别是 $1,2,\dots,n$ 。

节点 $i$ 和节点 $j$ 之间的边边权为 $|p_i-p_j|\times |i-j|$，其中 $|x|$ 表示 $x$ 的绝对值。

请问这个完全图的最小生成树的所有边的权值和是多少？

输入格式

从 pmst.in 文件读入数据。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $p_1,p_2,\dots,p_n$。

输出格式

输出到 pmst.out 文件。

输出一个整数，代表答案。

样例

5
3 2 5 1 4

8

样例 2

点击链接 ex_pmst2.in 和 ex_pmst2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，$1 \leq n\leq 5\times 10^4$。