| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 66 | 41 | 35 | 74.468% |
Перед уроком физкультуры класс из $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 3,000円$).
Во второй строке даны $n$ целых чисел $p_1, \ldots, p_n$ --- рост каждого ученика в шеренге (1ドル \le p_i \le n$). Гарантируется, что все $p_i$ различны.
Выведите одно целое число --- ответ на задачу.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 16 | $n \le 10$ |
| 2 | 28 | $n \le 50$ |
| 3 | 15 | $n \le 100$ |
| 4 | 23 | $n \le 600$ |
| 5 | 18 | $n \le 3,000円$ |
5 5 2 4 1 3
35
10 2 1 6 8 3 5 9 10 7 4
256
2 2 1
1
В первом примере ответ равен сумме следующих чисел:
Например, чтобы ученики, которые исходно стоят на позициях 4ドル$ и 5ドル$ и имеют рост 1ドル$ и 3ドル,ドル соответственно, оказались на расстоянии 4ドル,ドル учитель может выбрать отрезок с $l = 1$ и $r = 4$. Тогда последовательность учеников изменится следующим образом $[\underline{5, 2, 4, 1}, 3] \rightarrow [\underline{1, 2, 4, 5}, 3]$. Выбранный отрезок подчеркнут.