← 返回题目列表

Codeforces · 351/B

B. 杰夫和福里克

中文机器翻译题面 查看原题

杰夫已与福里克成为朋友。现在这两个人要玩一场非常有趣的游戏。

游戏开始时,Jeff 拿一张纸写下一个由 n 个数字组成的排列:p1、p2、...、pn。然后大家轮流出手,杰夫先出手。在移动过程中,杰夫选择了两个相邻的排列元素,然后男孩交换了它们。在移动过程中,Furic 扔一枚硬币,如果硬币显示“正面”,他会随机选择一对索引为 i 和 i + 1 的相邻元素(其中不等式 pi > pi + 1 成立),然后交换它们。但如果硬币显示“反面”,Furik 会随机选择一对索引为 i 和 i + 1 的相邻元素(满足不等式 pi < pi + 1),然后交换它们。如果硬币显示“正面”或“反面”,并且福里克有多种方式可以取相邻对,那么他统一取其中一对。如果福里克没有任何一双可以拿,他就会再抛一次硬币。当排列按升序排列时游戏结束。

Jeff 希望游戏尽快结束(也就是说,他希望两名玩家的移动次数尽可能少)。如果杰夫的移动效果最佳,请帮助杰夫找到游戏中移动次数的最小数学期望。

您可以认为硬币正面(或反面)的概率为 50%。

输入

第一行包含整数 n (1 ≤ n ≤ 3000)。下一行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 排列 p。数字之间用空格分隔。

输出

在一行中打印一个实际值 - 问题的答案。如果绝对误差或相对误差不超过 10 - 6,则答案将被视为正确。

示例

输入 #1

2
1 2

输出 #1

0.000000

输入 #2

5
3 5 2 4 1

输出 #2

13.000000

注意

在第一个测试中,序列已经排序,因此答案为 0。