Permutation Graph
Contest: Codeforces Global Round 21
Difficulty rating: 1900
Tags: binary search, constructive algorithms, data structures, divide and conquer, greedy, shortest paths

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<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<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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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

Example input:
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

Example output:
0
1
1
4
6

Editorial:
Denote $$$dis(x,y)$$$ as the length of the shortest path between $$$x$$$ and $$$y$$$.
Consider a position $$$i$$$ that $$$a_i=n$$$. Assume $$$i\ne 1$$$ and $$$i\ne n$$$. For a segment that passes $$$i$$$, its maximum element is always $$$a_i$$$. Thus, for $$$x<i<y$$$, $$$x$$$ and $$$y$$$ will never be directly connected by an edge. This means that when going from $$$1$$$ to $$$n$$$, we have to pass $$$i$$$. Let us solve recursively for $$$dis(1,i)$$$ and $$$dis(i,n)$$$. For example, we solve for $$$dis(1,i)$$$.
We already know that $$$a_i=n$$$, so $$$i$$$ is the maximum element in $$$[1,i]$$$. Consider the minimum element in $$$[1,i]$$$, suppose it is $$$a_j\ (j<i)$$$. From similar arguments, we can solve recursively for $$$dis(1,j)$$$ and $$$dis(j,i)$$$. However, note that $$$dis(j,i)$$$ equals to $$$1$$$: since $$$j$$$ and $$$i$$$ are respectively minimum and maximum in $$$[1,i]$$$, they have to be minimum and maximum in $$$[j,i]$$$ as well. So $$$i,j$$$ must be directly connected. Thus, we only need to solve recursively for $$$dis(1,j)$$$.
The process with $$$dis(i,n)$$$ is similar. Note that we will only call $$$dis(l,r)$$$ for $$$l=1$$$ or $$$r=n$$$ (if not, the return value is always 1), so it suffices to pre-compute prefix and suffix minimums and maximums.
The time complexity is $$$O(n)$$$.