题目内容

在一个自动化仓库中，有一条长度为 $n$ 的环形传送带，传送带上依次摆放着 $n$ 个货物，货物按固定顺序不断循环移动。第 $i$ 个货物的品质等级为 $c_i$（$1 \le i \le n$）。

操作员可以按传送带的运行方向，在任意时刻选择当前经过的货物进行收集。被收集的货物必须严格按照品质等级递增的顺序（即后一个货物的等级必须大于前一个货物的等级）。

由于传送带循环次数极多（可以视为 $10^9+1$ 次完整循环），操作员有非常多的机会来选择货物。请你计算，在这条无限循环的传送带上，操作员最多可以收集多少个货物，使得品质等级严格递增。

数据范围：

• 测试数据组数 $T$，满足 $1 \le T \le 10^4$。
• 传送带长度 $n$，$1 \le n \le 2 imes 10^5$，且所有测试数据的 $n$ 之和不超过 $2 imes 10^5$。
• 每个货物的品质等级 $c_i$ 均为整数，满足 $1 \le c_i \le n$。

输入描述

第一行输入一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。随后每组数据： 第一行包含一个整数 $n$（$1 \le n \le 2 imes 10^5$），表示传送带上的货物数量。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$），表示货物的品质等级。

输出描述

对于每组测试数据，输出一行一个整数，表示能够收集的满足严格递增品质等级的最多货物数量。

样例1

输入

1
5
2 3 1 2 4

输出

4

说明

传送带长度为 $n = 5$，品质等级序列为 $c = [2, 3, 1, 2, 4]$。由于传送带无限循环，操作员可以在不同圈中选取货物，只要满足严格递增即可。数组中出现过的不同品质等级有 1、2、3、4，它们可以按递增顺序依次被收集（例如第一圈收集 1，下一圈收集 2，再收集 3，最后收集 4）。因此，最多可收集的货物数量等于不同品质等级的个数，为 4。

样例2

输入

1
3
5 5 5

输出

1

说明

传送带长度 $n = 3$，品质等级序列为 $c = [5, 5, 5]$。所有货物等级均为 5，无法形成严格递增序列。无论循环多少次，操作员最多只能收集 1 个货物。答案为 1。

样例3

输入

1
1
1

输出

1

说明

边界情况：传送带长度 $n = 1$，唯一货物的品质等级为 1。操作员只能收集该货物，因此最多收集数量为 1。