409. Инверсии

Пусть $p_1$, $p_2$, $\ldots$, $p_n$ перестановка чисел от $1$ до $n$. Будем говорить, что пара индексов $(i, j)$ образует инверсию, если $i < j$ и $p_{i} > p_{j}$.

Задана некоторая перестановка $(p_1, \ldots, p_n)$, требуется определить среднее количество инверсий в перестановке, полученной из данной после одной перестановки пары элементов. При этом индексы переставляемых элементов выбираются равновероятно среди всех пар различных чисел от 1 до $n$.

В первой строке записано одно целое число $n$ ($2 \le n \le 2000$).

Во второй строке записаны $n$ целых чисел $p_1$, $p_2$, $\ldots$, $p_n$ ($1 \le p_i \le n$), все числа в строке различны.

Выведите несократимую дробь $a/b$, задающую значение среднего числа инверсий по всем возможным парам переставляемых индексов элементов.