思路与结论

• 只有“跨区间”的数对会受影响：

  • 新增逆序对：区间内的元素与区间右侧相同值形成的新逆序对（$a_i == a_j$ 且 $i$ 在区间内、$j$ 在区间右侧）。
  • 被消去的逆序对：区间左侧值为 $v+1$ 与区间内值为 $v$ 的数对（$a_p = a_q + 1$，$p$ 在区间左侧，$q$ 在区间内）。

• 将“选择区间 $[L,R]$ 并把区间内加 1”的收益定义为：

  • 收益 = 被消去对数 − 新增对数
  • 等价于：$sum_{q∈[L,R]} pre[L-1][a_q+1]$ − $sum_{q∈[L,R]} suf[R+1][a_q]$

题目内容

你有一个长度为 $n$ 的序列 $A:a_1,a_2,…,a_n$，你需要进行如下操作至多一次：

选择一个区间$[L,R](1≤L≤R≤n)$，将 $a_1,a_{L+1},...,a_R$ 全部加 $1$ 。即 $a_L,a_{L+1},...,a_R$ 均变为 $a_L+1,a_{L+1}+1,...,a_R+1$

设变化后的序列为 $B：b_1,b_2,…,b_n$，你需要最大化 $inv(A)-inv(B)$ ，其中 $inv()$ 函数表示该序列的逆序对数量，即满足 $i<j，a_1>a_j$ 的二元组 $(i,j)$ 个数。换句话说，你需要尽可能地减小序列 $A$ 的逆序对数量。

输入描述

第一行一个正整数 $T$ ，表示数据组数；

对于每一组数据，第一行一个正整数 $n$ ; 第二行 $n$ 个正整数 $a_1,a_2,...,a_n$，表示序列 $A$ 。

$1≤n≤10^5, 1≤T≤5, 1≤a_i≤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$ 。