背景

小zy在冒险是一不小心到了痞子龙的巢穴，让人气愤的是痞子龙搞偷袭，对他发起了”大物理催眠术“，当小zy醒来时竟然发现自己被绑了起来，看着巢穴外睡觉的痞子龙，他的火气蹭蹭往上涨，他觉得必须给痞子龙一点颜色瞧瞧，让它看看龙骑士是怎么产生的，为此，小zy决定要打通自己的任督一脉！

题目描述

在小zy体内的任督一脉上有一排 n 个能量源，每个能量源都有一个整数权重：a_1, a_2, ..., a_n。

小zy精通气功，他可以在任督一脉创建和移动气。这意味着他可以按任意顺序执行以下两种操作，次数不限：

1. 在能量源前创建一团气。
2. 将现有的气向左或向右移动一个位置。

当一团气位于尚未被打通的能量源前时（无论它是被创建还是被移动的），它会立即打通该能量源。如果能量源已经被打通过，气不会做任何操作——每个能量源只能被打通一次。

为了成功打通任督一脉，他需要以特定的顺序打通所有能量源：能量源权重的序列必须是非递增的。也就是说，如果 $b\_1, b\_2, ..., b\_n$ 是打通能量源的顺序对应的权重，那么必须满足 $b\_1≥b\_2≥...≥b\_n$。

但是痞子龙还在外面等着他，小zy想创建最少的气，以便能够以有效顺序打通所有能量源。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 t （$1 \le t \le 10^{4}$）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 n （$1 \le n \le 2*10^{5}$）——能量源的数量。

每个测试用例的第二行包含 n 个整数 $a\_1, a\_2, ..., a\_n$ （$1 \le a\_i \le 10^{9}$）——能量源的权重。

保证所有测试用例的 n 之和不超过 $2*10^{5}$。

输出格式

对于每个测试用例，输出一个整数——为了以有效顺序打通所有能量源需要创建的最少气的数量。

样例

输入 #1

4
5
4 3 2 1 5
3
1 1 1
6
7 8 1 5 9 2
10
1 7 9 7 1 10 2 10 10 7

输出 #1

2
1
2
3

说明

在第一个测试用例中，小zy可以按以下方式操作：

1. 在第五个能量源（权重为 5）前创建一团气。
2. 在第一个能量源（权重为 4）前创建第二团气。
3. 将第二团气从第一个能量源移动到第二个能量源（权重为 3）。
4. 将第二团气从第二个能量源移动到第三个能量源（权重为 2）。
5. 将第一元气从第五个能量源移动到第四个能量源（权重为 1）。

这样，能量源打通的顺序将是 $5→4→3→2→1$，满足要求。可以证明，创建的气数量是最小的。

限制

时间限制：2s 内存限制：250MB