CF1696D.Permutation Graph

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

You are given a permutation of $1,2,\dots,n$, $[a_1,a_2,\dots,a_n]$. For integers $i$, $j$ such that $1\le i \lt j\le n$, define $\operatorname{mn}(i,j)$ as $\min\limits_{k=i}^j a_k$, and define $\operatorname{mx}(i,j)$ as $\max\limits_{k=i}^j a_k$.

Let us build an undirected graph of $n$ vertices, numbered $1$ to $n$. For every pair of integers $1\le i \lt j\le n$, if $\operatorname{mn}(i,j)=a_i$ and $\operatorname{mx}(i,j)=a_j$ both holds, or $\operatorname{mn}(i,j)=a_j$ and $\operatorname{mx}(i,j)=a_i$ both holds, add an undirected edge of length $1$ between vertices $i$ and $j$.

In this graph, find the length of the shortest path from vertex $1$ to vertex $n$. We can prove that $1$ and $n$ will always be connected via some path, so a shortest path always exists.

排列是指由 $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]$。对于满足 $1\le i \lt j\le n$ 的整数 $i,j$，定义 $\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 \lt j\le n$ 的整数 $i,j$，若同时满足 $\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$ 总是通过某条路径连通，因此最短路径一定存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5\cdot 10^4$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\le n\le 2.5\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1\le a_i\le n$). It's guaranteed that $a$ is a permutation of $1$, $2$, $\dots$, $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single line containing one integer — the length of the shortest path from $1$ to $n$.

对于每个测试用例，输出一行，包含一个整数——从节点 $1$ 到节点 $n$ 的最短路径长度。

The following are illustrations of constructed graphs in example test cases.

the constructed graph in test case 1

the constructed graph in test case 2

the constructed graph in test case 3

the constructed graph in test case 4

the constructed graph in test case 5

以下是示例测试用例中构造的图的示意图。

测试用例 1 中构造的图

测试用例 2 中构造的图

测试用例 3 中构造的图

测试用例 4 中构造的图

测试用例 5 中构造的图