## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Permutation Graph Codeforces Solution | Codeforces Problem Solution 2022

D. Permutation Graph
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

You are given a permutation of $1,2,\dots ,n$$\left[{a}_{1},{a}_{2},\dots ,{a}_{n}\right]$. For integers $i$$j$ such that $1\le i, define $\mathrm{mn}\left(i,j\right)$ as $\underset{k=i}{\overset{j}{min}}{a}_{k}$, and define $\mathrm{mx}\left(i,j\right)$ as $\underset{k=i}{\overset{j}{max}}{a}_{k}$.

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

Solution Click Below:-  👉
👇👇👇👇👇

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

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}$$\dots$${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

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