题目描述

译自 ROI 2022 Day1 T1. Урок физкультуры

在体育课前，班上共有 $n$ 名学生排成一排。每个学生的身高都不一样。从左往右数队列中第 $i$ 位是身高为 $p_i$ 的学生（其中 $i = 1, 2, \dots, n$，且 $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]$。

通过这样的操作，老师希望能让两个特定的学生尽可能远离对方。学生之间的距离等于他们在队列中的位置差。对于每一对学生，老师会计算通过一次排序操作后他们能达到的最大距离。请帮助老师找出所有学生对之间最大距离的总和。

更正式地说，考虑初始位于位置 $i$ 和 $j$ 的学生。记 $d(i, j)$ 为通过选择一个区间并进行排序后，能使他们达到的最大距离。需要计算的是：

$$\sum\limits_{i = 1}^{n - 1} \sum\limits_{j = i + 1}^{n} d(i, j) $$

输入格式

第一行是一个整数 $n\ (2 \le n \le 3000)$ 表示班级中的学生数量。

第二行是 $n$ 个整数 $p_1, \ldots, p_n\ (1 \le p_i \le n)$，表示每个学生的身高。保证 $p_i$ 互不相同的。

输出格式

输出一个整数，表示问题的答案。

5
5 2 4 1 3

35

在第一个样例中，答案等于以下数值的总和：

• $d(1, 2) = 3$
• $d(1, 3) = 4$
• $d(1, 4) = 4$
• $d(1, 5) = 4$
• $d(2, 3) = 3$
• $d(2, 4) = 3$
• $d(2, 5) = 4$
• $d(3, 4) = 3$
• $d(3, 5) = 3$
• $d(4, 5) = 4$

例如，为了让最初站在第 $4,5$ 位学生之间的距离达到 $4$，老师可以选择从第 $1$ 位到第 $4$ 位的区间。这样，学生的排列将变为 $[\underline{5, 2, 4, 1}, 3] \rightarrow [\underline{1, 2, 4, 5}, 3]$。选定的区间用下划线标出。

10
2 1 6 8 3 5 9 10 7 4

256

2
2 1

1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	附加限制	子任务依赖
$1$	$16$	$n \le 10$	$0$
$2$	$28$	$n \le 50$	$1$
$3$	$15$	$n \le 100$	$0, 1, 2$
$4$	$23$	$n \le 600$	$0, 1-3$
$5$	$18$	$n \le 3000$	$0, 1-4$