Задача C1. Урок физкультуры ≡

Условие

Перед уроком физкультуры класс из n учеников построился в одну шеренгу. Все ученики в классе имеют разный рост. На i-м слева месте в шеренге стоит ученик с ростом p_i (i = 1, 2, …, n, 1 ≤ p_i ≤ n).

Учитель физкультуры в начале урока может захотеть изменить порядок учеников в шеренге. Для этого он может ровно один раз выполнить следующую операцию: выбрать отрезок шеренги с l-й по r-ю позицию (1 ≤ l ≤ r ≤ n), и отсортировать учеников на этом отрезке по возрастанию роста слева направо. Например, если n = 5 и изначально ученики стояли в порядке [5, 2, 4, 1, 3], а учитель выбрал l = 1 и r = 4, то после сортировки ученики будут стоять в порядке [1, 2, 4, 5, 3].

Используя эту операцию, учитель может постараться добиться того, чтобы два определенных ученика оказались как можно дальше друг от друга. Расстояние между учениками равно разности номеров позиций, на которых они стоят. Для каждой пары учеников учитель вычисляет максимальное расстояние, на котором они могут оказаться после выполнения одной операции сортировки отрезка. Помогите учителю найти сумму этих значений.

Более формально, рассмотрим учеников, которые исходно расположены на позициях i и j. Обозначим за d(i, j) максимальное расстояние между ними, которого учитель может добиться, выбрав отрезок и выполнив сортировку. Необходимо вычислить: n − 1∑i = 1n∑j = i + 1d(i, j).

Формат входных данных

В первой строке дано одно целое число n — количество учеников в классе (2 ≤ n ≤ 3 000).

Во второй строке даны n целых чисел p₁, …, p_n — рост каждого ученика в шеренге (1 ≤ p_i ≤ n). Гарантируется, что все p_i различны.

Формат выходных данных

Ограничения

Система оценки

Примеры тестов

5
5 2 4 1 3

35

10
2 1 6 8 3 5 9 10 7 4

256

2
2 1

1