题目描述

在体育课前，一个由 $n$ 名学生组成的班级排成了一列。班级中的所有学生身高不同。在队列的第 $i(1\le i\le n)$ 个位置上站着一个身高为 $p_i(1\le p_i\le n)$ 的学生。

体育老师在课堂开始时可能想要改变学生在队列中的顺序。为此，他可以执行以下操作一次：选择从第 $l$ 到第 $r$ 位置（$1 \le l \le r \le n$）的一段队列，并将这段队列中的学生按照从左到右的升序进行排序。例如，如果 $n = 5$，并且最初学生们的顺序是 $[5, 2, 4, 1, 3]$，而老师选择 $l = 1,r = 4$，则在排序后学生们的顺序将变为 $[1, 2, 4, 5, 3]$。

老师想要使得两个特定的学生尽可能远离彼此。学生之间的距离等于他们所站位置的编号之差。对于每对学生，老师想要知道在执行一次排序操作后他们可以达到的最大距离。请帮助老师算出这些值的总和。

如果用 $d(i, j)$ 表示老师通过选择一段队列并进行排序可以达到的刚开始在位置 $i$ 和 $j$ 上的学生之间的最大距离，需要计算的就是 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

输入格式

第一行包含一个整数 $n$，表示班级中的学生数量（$2 \le n \le 3,000$）。

第二行包含 $n$ 个整数 $p_1,\dots , p_n$，表示队列中每个学生的身高（$1 \le p_i \le n$）。

保证所有 $p_i$ 都是不同的。

输出格式

输出一个整数，表示问题的答案，即 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

输入输出样例 #1

输入 #1

5
5 2 4 1 3

输出 #1

35

输入输出样例 #2

输入 #2

10
2 1 6 8 3 5 9 10 7 4

输出 #2

256

输入输出样例 #3

输入 #3

2
2 1

输出 #3

1

说明/提示

在样例一中，答案是以下数字之和：

例如，为了使最初位于位置 $4$ 和 $5$ 上且身高分别为 $1$ 和 $3$ 的学生之间的距离为 $4$，老师可以选择 $l = 1,r = 4$，然后，学生序列将从 $[\underline{5, 2, 4, 1}, 3]$ 变为 $[\underline{1, 2, 4, 5}, 3]$。被选择的段已经用下划线标注出来。