杰夫已与福里克成为朋友。现在这两个人要玩一场非常有趣的游戏。
游戏开始时,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。