P3392.第1题-减小逆序对
题目内容
你有一个长度为 n 的序列 A:a1,a2,…,an，你需要进行如下操作至多一次：
选择一个区间[L,R](1≤L≤R≤n)，将 a1,aL+1,...,aR 全部加 1 。即 aL,aL+1,...,aR 均变为 aL+1,aL+1+1,...,aR+1
设变化后的序列为 B：b1,b2,…,bn，你需要最大化 inv(A)−inv(B) ，其中 inv() 函数表示该序列的逆序对数量，即满足 i<j，a1>aj 的二元组 (i,j) 个数。换句话说，你需要尽可能地减小序列 A 的逆序对数量。
输入描述
第一行一个正整数 T ，表示数据组数；
对于每一组数据，第一行一个正整数 n ; 第二行 n 个正整数 a1,a2,...,an，表示序列 A 。
1≤n≤105,1≤T≤5,1≤ai≤n
输出描述
对于每一组数据，输出一个整数，表示最大的 inv(A)−inv(B) 。
样例1
输入
3
5
4 2 3 1 5
5
1 2 3 4 5
3
2 1 1
输出
2
0
2
说明
第一组数据，选择区间 [3,4] ，变化后的序列为 [4,2,4,2,5,5] ，逆序对数量为3；变化前逆序对数量为 5 。
第二组数据，选择任意区间都不会减小逆序对数量。
第三组数据，选择区间 [2,3] ，变化后的序列为 [2,2,2]，逆序对数量为 0 ；变化前逆序对数量为 2 。
