P11096 [ROI 2022] 体育课 (Day 1)

翻译自 [ROI 2022 D1T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。 在体育课前，一个由 $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)$。

在样例一中，答案是以下数字之和：  例如，为了使最初位于位置 $4$ 和 $5$ 上且身高分别为 $1$ 和 $3$ 的学生之间的距离为 $4$，老师可以选择 $l = 1,r = 4$，然后，学生序列将从 $[\underline{5, 2, 4, 1}, 3]$ 变为 $[\underline{1, 2, 4, 5}, 3]$。被选择的段已经用下划线标注出来。 | Subtask | 分值 | $n\le$ | | :----------: | :----------: | :----------: | | $1$ | $16$ | $10$ | | $2$ | $28$ | $50$ | | $3$ | $15$ | $100$ | | $4$ | $23$ | $600$ | | $5$ | $18$ | $3000$ |