解题思路
我们只允许至多一次把一个子段 [l,r] 反转。逆序对只与相对顺序有关。把 [l,r] 反转时：
- 区间外与区间内的“跨区间对”在反转前后依然满足“左下标 < 右下标”，比较的两值也没变，因此这部分逆序对数量不变。
- 唯一会改变的是区间内部两两成对的关系。
设区间长度为 k = r-l+1，区间内
P3726.第4题-数组逆序反转
题目内容
给定一个长度为 n 的整数数组 a={a1,a2,...,an}。你可以进行至多一次操作：选择一个区间 [l,r] 并将该区间内的元素顺序反转；也可以不进行任何操作。
记逆序对为满足 1≤i<j≤n 且 ai>aj 的有序对数量(相等不计入逆序)。
请你在允许至多一次区间反转的前提下，使逆序对数量尽可能小，并输出该最小值。
- 顺序反转的定义：选择 [l,r] 后，将段内顺序由 [al,al+1,...,ar] 变为 [ar,ar−1,...,al] ；区间外元素及其相对顺序不变。若 l=r 等价于不操作。
输入描述
第一行输入一个整数 n(1≦n≦2×103) ；
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109) 。
输出描述
输出一个整数，表示在至多一次区间反转后，数组可能达到的最小逆序对数量。
样例1
输入
5
2 1 5 3 4
输出
2
说明
选择反转区间 [1,2] ，得到 [1,2,5,3,4] ，逆序对为 (5,3)，(5,4) ，数量为 2 。
