#P18052. Dolls 2

Dolls 2

Dolls 2

有 nn 个大小互不相同的套娃,从左到右排列,初始每个格子中只有一个套娃,第 ii 个的大小为 aia_i。

对于当前第 ii 个格子,记其中最小、最大的套娃大小分别为 li,ril_i,r_i。只有当

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

时,才允许合并相邻的两个格子 i,i+1i,i+1。合并后,一个格子包含原来两个格子中的所有套娃,其右侧格子依次左移。

你必须不断进行合法合并,直到再也无法合并任何两个相邻格子。求整个过程中最少需要进行多少次合并。

输入格式

第一行整数 TT,1≤T≤1041\le T\le10^4。每个用例包含两行:

  • 一个整数 nn,2≤n≤1062\le n\le10^6。
  • nn 个整数 a1,…,ana_1,\ldots,a_n,它们是 1,…,n1,\ldots,n 的一个排列。

所有用例的 nn 之和不超过 10610^6。

输出格式

每个用例输出一行一个整数,表示最少合并次数。

样例

输入:

5
5
1 2 3 5 4
5
1 2 3 4 5
5
1 3 5 4 2
5
1 5 2 4 3
5
1 2 4 3 5

输出:

3
4
3
2
3