Problem Description

Translated from ROI 2022 D1T1。

Before the PE class, a class of $n$ students stands in a line. All students in the class have different heights. At position $i(1\le i\le n)$ in the line, there is a student of height $p_i(1\le p_i\le n)$.

At the beginning of the class, the PE teacher may want to change the order of the students in the line. To do this, he can perform the following operation once: choose a segment of the line from position $l$ to position $r$ ($1 \le l \le r \le n$), and sort the students in this segment in increasing order from left to right. For example, if $n = 5$ and the initial order is $[5, 2, 4, 1, 3]$, and the teacher chooses $l = 1,r = 4$, then after sorting the order becomes $[1, 2, 4, 5, 3]$.

The teacher wants to make two specific students as far apart from each other as possible. The distance between two students is the difference between the indices of the positions where they stand. For every pair of students, the teacher wants to know the maximum distance they can achieve after performing the sorting operation once. Please help the teacher compute the sum of these values.

If $d(i, j)$ denotes the maximum distance that the teacher can achieve between the students who initially stand at positions $i$ and $j$ by choosing a segment and sorting it, you need to compute $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

Input Format

The first line contains an integer $n$, the number of students in the class ($2 \le n \le 3,000$).

The second line contains $n$ integers $p_1,\dots , p_n$, representing the heights of the students in the line ($1 \le p_i \le n$).

It is guaranteed that all $p_i$ are distinct.

Output Format

Output one integer, the answer to the problem, i.e., $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

5
5 2 4 1 3

35

10
2 1 6 8 3 5 9 10 7 4

256

2
2 1

1

Hint

In Sample 1, the answer is the sum of the following numbers:

For example, to make the distance between the students who were initially at positions $4$ and $5$ with heights $1$ and $3$ equal to $4$, the teacher can choose $l = 1,r = 4$. Then the sequence changes from $[\underline{5, 2, 4, 1}, 3]$ to $[\underline{1, 2, 4, 5}, 3]$. The chosen segment is underlined.

Translated by ChatGPT 5