排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
给出的排列为 $$$1,2,\dots,n$$$, $$$[a_1,a_2,\dots,a_n]$$$。对于整数 $$$i$$$、$$$j$$$ 使得 $$$1\le i<j\le n$$$,将 $$$\operatorname{mn}(i,j)$$$ 定义为 $$$\min\limits_{k=i}^j a_k$$$,并将 $$$\operatorname{mx}(i,j)$$$ 定义为$$$\max\limits_{k=i}^j a_k$$$。
让我们构建一个由 $$$n$$$ 个顶点组成的无向图,编号为 $$$1$$$ 到 $$$n$$$。对于每对整数 $$$1\le i<j\le n$$$,如果 $$$\operatorname{mn}(i,j)=a_i$$$ 和 $$$\operatorname{mx}(i,j)=a_j$$$ 都成立,或者 $$$\operatorname{mn}(i,j)=a_j$$$ 和$$$\operatorname{mx}(i,j)=a_i$$$ 都成立,在顶点 $$$i$$$ 和 $$$j$$$ 之间添加一条长度为 $$$1$$$ 的无向边。
在此图中,求从顶点 $$$1$$$ 到顶点 $$$n$$$ 的最短路径的长度。我们可以证明 $$$1$$$ 和 $$$n$$$ 总是通过某条路径相连,因此最短路径总是存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2.5\cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1\le a_i\le n$$$)。保证 $$$a$$$ 是 $$$1$$$、$$$2$$$、$$$\dots$$$、$$$n$$$ 的排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,打印一行包含一个整数 - 从 $$$1$$$ 到 $$$n$$$ 的最短路径的长度。
示例
输入 #1
5 1 1 2 1 2 5 1 4 2 3 5 5 2 1 5 3 4 10 7 4 8 1 6 10 3 5 2 9
输出 #1
0 1 1 4 6
注意
以下是示例测试用例中构造图的说明。
测试用例1中构造的图
测试用例2中构造的图
测试用例3中构造的图
测试用例4中构造的图
测试用例5中构造的图