题目描述

猫猫刚刚获得了 $n$ 个大小互不相同的积木块。他将这些积木块从左到右摆成了一排，第 $i$ 个位置上包含一个大小为 $a_i$ 的积木块。

设第 $i$ 格上的最小积木块的大小为 $l_i$ ，最大积木块的大小为 $r_i$ 。两个相邻格子 $i$ 和 $i+1$ 上的积木块能合并，当且仅当 $r_i<l_{i+1}$ 或 $r_{i+1} <l_i$ 。新的积木块将包含原有第 $i$ 格和第 $i+1$ 格上的所有积木块，并被放置在第 $i$ 格上。所有编号大于 $i+1$ 的格子上的积木块都将向左移动一格以填补空缺。

例如，当 $n=4,a=[2,1,4,3]$ 时，猫猫可以：

1. 合并第1格和第2格上的积木块。此时剩余三个格子上的积木块大小分别为 $[(1,2),(4),(3)]$ 。
2. 合并第2格和第3格上的积木块。此时剩余两个格子上的积木块大小分别为 $[(1,2),(3,4)]$ 。
3. 合并第1格和第2格上的积木块。此时所有积木块都被合并到了一个格子上。

在最优策略下，猫猫最多能执行多少次合并操作？

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T (1≤T≤10^4)$ 。每组测试数据的格式如下：

第一行包含一个整数 $n(1≤n≤10^5)$ ，表示积木块的数量。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n (1 ≤a_i ≤n, ∀i\neq j,a_i \neq a_j)$ ，表示初始状态下每个位置上的积木块的大小。

在每个测试文件内，保证所有测试数据的 $n$ 之和不超过 $10^5$ 。

输出格式

对于每组数据，输出一行一个整数，表示最多能执行的合并操作数。

样例

8
4
2 1 4 3
4
1 4 2 3
4
3 1 4 2
5
1 3 5 2 4
5
1 4 2 5 3
5
2 5 3 1 4
6
1 3 6 5 2 4
6
2 5 1 3 6 4

3
3
2
3
3
3
4
4