CF351B Jeff and Furik

Jeff 和 Furik 成为了朋友。现在这两个人要玩一个非常有趣的游戏。 游戏开始时，Jeff 拿出一张纸，写下了一个由 $n$ 个数字组成的排列：$p_1, p_2, \ldots, p_n$。接下来两人轮流进行操作，Jeff 先手。在自己的回合，Jeff 可以选择任意一对相邻的排列元素，将它们交换位置。在 Furik 的回合，他会掷一枚硬币，如果硬币为“正面”，他会在所有 $p_i > p_{i+1}$ 的相邻对 $(i, i+1)$ 中，等概率随机选择一对进行交换；如果硬币为“反面”，他会在所有 $p_i < p_{i+1}$ 的相邻对 $(i, i+1)$ 中，等概率随机选择一对进行交换。如果 Furik 掷出某一面但没有可选对，则他会重新掷一次。游戏在排列变为升序时结束。 Jeff 想让游戏尽快结束（即让两人总的操作步数尽可能少）。请你帮助 Jeff 计算，在他最优操作的情况下，本游戏的最小期望操作次数。 你可以认为硬币的正反面概率均为 $50\%$。

第一行包含一个整数 $n$ ($1 \le n \le 3000$)。 第二行包含 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）——排列 $p$。数字以空格分隔。

输出一个实数，表示本问题的答案。若输出的答案与标准答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

在第一个测试样例中，序列已经升序排列，因此答案是 $0$。 由 ChatGPT 5 翻译