Джефф — новый друг Фурика. Сейчас ребята собрались поиграть в одну увлекательную игру.

В самом начале игры Джефф записывает на листке перестановку, состоящую из n чисел: p₁, p₂, ..., p_n. Далее ребята по очереди делают ходы, первым ходит Джефф. На своем ходу Джефф выбирает два соседних элемента перестановки и меняет их местами. На своем ходу Фурик подбрасывает монетку, и если монетка выпадает «орлом», то Фурик выбирает случайную пару соседних элементов с номерами i и i + 1, для которых верно неравенство p_i > p_i + 1, и меняет их местами. Если же монетка выпала «решкой», то Фурик выбирает случайную пару соседних элементов с номерами i и i + 1, для которых верно неравенство p_i < p_i + 1, и меняет их местами. Если после того как монетка выпала «орлом» или «решкой» у Фурика есть несколько вариантов, какую пару соседних элементов взять, то он равновероятно выбирает один из вариантов. Если у Фурика нет ни одного варианта, то он подбрасывает монетку еще раз. Игра заканчивается, когда перестановка оказывается отсортированной по возрастанию.

Джефф хочет, чтобы игра закончилась как можно быстрее (то есть было совершено как можно меньше ходов). Помогите Джеффу найти минимальное математическое ожидание количества ходов в игре, если он действует оптимально.

Считайте, что монетка выпадает орлом (и решкой) с вероятностью 50 процентов.