Задача . E. Инверсии после перемешивания

Дана перестановка целых чисел от 1 до n. Ровно один раз с перестановкой проделывается следующее преобразование: выбирается некоторый случайный отрезок и все его элементы перемешиваются. Формально:

1. Выбирается случайный подотрезок (непрерывная подпоследовательность) от l до r включительно. При этом все отрезков равновероятны.
2. Пусть k = r - l + 1, то есть длине выбранного отрезка. Выбирается случайная перестановка чисел от 1 до k, p₁, p₂, ..., p_k. При этом все k! перестановок равновероятны.
3. К элементам отрезка применяется данная перестановка, то есть перестановка a₁, a₂, ..., a_l - 1, a_l, a_l + 1, ..., a_r - 1, a_r, a_r + 1, ..., a_n переходит в перестановку a₁, a₂, ..., a_l - 1, a_{l - 1 + p1}, a_{l - 1 + p2}, ..., a_{l - 1 + pk - 1}, a_{l - 1 + pk}, a_r + 1, ..., a_n.

Инверсией в перестановке называется пара элементов (не обязательно соседних), нарушающих порядок сортировки по возрастанию, то есть количество инверсий равно количеству пар (i, j), таких что i < j и a_i > a_j. Найдите математическое ожидание количества инверсий после выполнения данной операции.