解题思路

先看一次操作会改变什么。

选择分界点 $i$ 和整数 $x$ 后：

• 前缀 $a_1 \sim a_i$ 的每个数都变成 $a_j-x$
• 后缀 $a_{i+1} \sim a_n$ 的每个数都变成 $a_j+x$

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}。你可以进行如下操作至多一次(也可以不进行任何操作)：

• 选择一个下标 $1≤i<n$ 和任意整数 $x$ ，将区间 $a_1,a_2,...,a_i$ 中的每个元素减少 $x$ ，同时将区间 $a_{i+1},a_{i+2},...,a_n$ 中的每个元素增加 $x$ 。

请你最小化操作结束后数组中的逆序对个数，并输出这个最小值。

【名词解释】

逆序对：对在序列中，若存在两个下标 $p,q$ 满足 $p<q$ 且 $a_p>a_q$，则称 ($p,q$) 为一个逆序对。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ 表示数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$ 表示数组长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤n)$ 表示数组 $a$ 。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示最多可以进行的操作次数。

样例1

输入

2
5
2 1 5 3 4
4
4 3 2 1

输出

1
2

说明

• 对于第一组数据，选择 $i=3$ ，以及一个整数 $1$ 。数组变为 {$1,0,4,4,5$} 此时逆序对仅有 $(1,2)$ 可以证明没有其他操作可以使逆序对更小。