#P18233. Dolls

Dolls

Dolls

David 得到了 nn 个大小互不相同的俄罗斯套娃,并将它们从左到右排成一行。最初第 ii 个位置只有一个大小为 aia_i 的套娃。

一个位置中可能已经包含多个套娃。设当前第 ii 个位置中最小套娃的大小为 lil_i,最大套娃的大小为 rir_i。当且仅当

ri<li+1或ri+1<lir_i<l_{i+1}\quad\text{或}\quad r_{i+1}<l_i

时,可以将相邻两个位置 ii 和 i+1i+1 中的套娃合并:新位置包含这两个原位置中的全部套娃,放在位置 ii;原来在 i+1i+1 之后的所有位置向左移动一位。

例如,初始排列为 [2,1,4,3][2,1,4,3] 时,可以依次进行:

  1. 合并前两个位置,得到 [(1,2),(4),(3)][(1,2),(4),(3)]。
  2. 合并后两个位置,得到 [(1,2),(3,4)][(1,2),(3,4)]。
  3. 合并剩余两个位置,将全部套娃放在一起。

采用最优策略,最多可以进行多少次合并?

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含两行:

  • 第一行一个整数 nn。
  • 第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示最初的套娃大小。

数据范围:

  • 1≤T≤1041\le T\le10^4;
  • 1≤n≤1051\le n\le10^5;
  • 1≤ai≤n1\le a_i\le n,且任意两个 aia_i 不同,即 aa 为 1..n1..n 的排列;
  • 同一输入文件所有测试用例的 nn 之和不超过 10510^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