题目内容

多多在这座火车站担任调度。

今天驶入的货运列车一共挂了 $L$ 节车厢，自左向右记作第 $1,2,\dots,L$ 节。第 $t$ 节所装货物的卸货等级记为 $B_t$，各节的卸货等级两两不同。

为了让后面卸货更顺手，多多要把整列车厢排成卸货等级自左向右严格变大的样子。

站台上已经备好两套专用器具：

• 小型调转轨道：挑出紧挨着的 $2$ 节车厢，把这两节的前后次序倒过来。这套设备体积很小，省力机构装不进去，只能靠电机带动，每开动一次就要用掉 $1$ 个单位的电。
• 三节回旋轨道：挑出紧挨着的 $3$ 节车厢，把这三节的前后次序整段倒过来。轨道配了加长摇柄和配重，调度员用不大的力气就能让它启动，所以完全不耗电。

这两种设备要用几次、谁先谁后，以及压在列车哪一段紧邻车厢上，多多都能自由安排。请算出排成上述目标次序时，最少要用掉多少单位的电。

输入描述

首行一个整数 $Q$（$1 \le Q \le 10$），表示测试一共有几组。

后面共 $Q$ 行，每一行对应一组。行首整数 $L$（$1 \le L \le 10^5$）是本组车厢节数，随后 $L$ 个整数 $B_1,B_2,\dots,B_L$（$0 \le B_t \le 10^9$）是各节的卸货等级。全部 $B_t$ 彼此不相等，读进来的每个数都是整数。

输出描述

写出 $Q$ 行，每行一个整数，对应该组最少消耗的电量。

样例1

输入

2
4 1 3 2 4
3 3 2 1

输出

1
0

说明

第一组卸货等级是 $1,3,2,4$。小型调转轨道把第 $2$ 节和第 $3$ 节倒序后得到 $1,2,3,4$，耗电 $1$。不耗电时，只能交换第 $1$ 节与第 $3$ 节，或者交换第 $2$ 节与第 $4$ 节。交换之后奇数位仍是 $1$ 和 $2$，而目标次序的奇数位是 $1$ 和 $3$，所以耗电不能是 $0$。

第二组卸货等级是 $3,2,1$。三节回旋轨道把这三节整段倒序，得到 $1,2,3$，耗电 $0$。