РОИ: 1 тур

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

Учитель физкультуры хочет, чтобы ученики с номерами \(a\) и \(b\) стояли как можно дальше друг от друга, потому что они постоянно болтают и мешают проводить урок. Для этого, он может ровно один раз выполнить следующее действие. Выбрать отрезок шеренги с \(l\)-й по \(r\)-ю позицию (\(1 \le l \le r \le n\)), то есть \(p_l\), \(p_{l + 1}\), ..., \(p_r\). И переупорядочить учеников на этом отрезке в порядке возрастания роста слева направо. Например, если \(n = 5\) и изначально ученики стояли в порядке \(3\), \(1\), \(5\), \(2\), \(4\), а учитель выбрал \(l = 2\) и \(r = 5\), то после выполнения действия, ученики будут стоять в порядке \(3\), \(1\), \(2\), \(4\), \(5\).

Когда учитель выберет номера двух учеников, он выполнит действие оптимальным образом, чтобы расстояние между этими двумя учениками стало максимальным возможным. Расстояние между учениками равно разности номеров позиций, на которых они стоят. Но учитель еще не определился, какую именно пару учеников выбрать. Поэтому, вычислите сумму по всем парам учеников \(a\) и \(b\) (\(1 \le a < b \le n\)) расстояния, на котором они окажутся, если учитель выберет их и выполнит действие оптимальным образом.

Более формально, обозначим за \(d(a, b)\) максимальное расстояние между учениками \(a\) и \(b\), которого учитель может добиться, выполнив действие. Тогда вам нужно вычислить: \(\)\sum\limits_{a = 1}^{n - 1} \sum\limits_{b = a + 1}^{n} d(a, b)\(\)