解题思路

我们只允许至多一次把一个子段 [l,r] 反转。逆序对只与相对顺序有关。把 [l,r] 反转时：

• 区间外与区间内的“跨区间对”在反转前后依然满足“左下标 < 右下标”，比较的两值也没变，因此这部分逆序对数量不变。
• 唯一会改变的是区间内部两两成对的关系。

设区间长度为 k = r-l+1，区间内

• invSeg：大于对数（ai > aj）；

题目内容

给定一个长度为 $n$ 的整数数组 $a=${$a_1,a_2,...,a_n$}。你可以进行至多一次操作：选择一个区间 $[l,r]$ 并将该区间内的元素顺序反转；也可以不进行任何操作。

记逆序对为满足 $1≤i < j≤n$ 且 $a_i>a_j$ 的有序对数量(相等不计入逆序)。

请你在允许至多一次区间反转的前提下，使逆序对数量尽可能小，并输出该最小值。

• 顺序反转的定义：选择 $[l,r]$ 后，将段内顺序由 $[a_l,a_{l+1},...,a_r]$ 变为 $[a_r,a_{r-1},...,a_l]$ ；区间外元素及其相对顺序不变。若 $l=r$ 等价于不操作。

输入描述

第一行输入一个整数 $n(1 ≦n≦ 2×10^3)$ ；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦ a_i≦ 10^9)$ 。

输出描述

输出一个整数，表示在至多一次区间反转后，数组可能达到的最小逆序对数量。

样例1

输入

5
2 1 5 3 4

输出

2

说明

选择反转区间 $[1,2]$ ，得到 $[1,2,5,3,4]$ ，逆序对为 $(5,3)，(5,4)$ ，数量为 $2$ 。