Вам дана перестановка из n чисел p1, p2, ..., pn. Мы совершаем k операций следующего типа: выбираем равновероятно случайным образом два индекса l и r (l ≤ r) и меняем порядок элементов pl, pl + 1, ..., pr на обратный. Ваша задача — определить математическое ожидание количества инверсий в итоговой перестановке.
Выходные данные
Выведите ответ на задачу с абсолютной или относительной погрешностью не более чем 1e - 9.
Примечание
Рассмотрим первый пример. В перестановке (1, 2, 3) (которая изначально не содержит инверсий) будет выбран один интервал и порядок его элементов будет изменен на обратный. С вероятностью 
, интервал будет состоять из одного элемента и перестановка не изменится. С вероятностью 
мы поменяем местами первые два элемента и получим перестановку (2, 1, 3) с одной инверсией. С такой же вероятностью мы можем выбрать интервал, состоящий из последних двух элементов, что приведет к перестановке (1, 3, 2), в которой тоже одна инверсия. Наконец, с вероятностью выбранный случайным образом интервал будет содержать все элементы, что приведет к перестановке (3, 2, 1) с тремя инверсиями. Таким образом, мат.ожидание количества инверсий равно 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2 3
|
0.833333333333333
|
|
2
|
3 4
1 3 2
|
1.458333333333334
|