[Solution] Permutation Graph Codeforces Solution

[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$n$ distinct integers from 1$1$ to n$n$ in arbitrary order. For example, [2,3,1,5,4]$[2,3,1,5,4]$ is a permutation, but [1,2,2]$[1,2,2]$ is not a permutation (2$2$ appears twice in the array) and [1,3,4]$[1,3,4]$ is also not a permutation (n=3$n=3$ but there is 4$4$ in the array).

You are given a permutation of 1,2,…,n$1,2,\dots ,n$, [a1,a2,…,an]$[a_1,a_2,\dots ,a_n]$. For integers i$i$, j$j$ such that 1≤i<j≤n$1\le i<j\le n$, define mn(i,j)$\mathrm{mn}(i,j)$ as mink=ijak$\underset{k=i}{\overset{j}{min}}{a}_k$, and define mx(i,j)$\mathrm{mx}(i,j)$ as maxk=ijak$\underset{k=i}{\overset{j}{max}}{a}_k$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

In this graph, find the length of the shortest path from vertex 1$1$ to vertex n$n$. We can prove that 1$1$ and n$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$t$ (1≤t≤5⋅104$1\le t\le 5\cdot {10}^4$). Description of the test cases follows.

NIT orz! Codeforces Solution

NIT Destroys the Universe Codeforces Solution 

Fishingprince Plays With Array Codeforces Solution

Permutation Graph Codeforces Solution

Placing Jinas Codeforces Solution 

Tree Recovery Codeforces Solution

Fishingprince Plays With Array Again Codeforces Solution

Maximum Product? Codeforces Solution

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

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

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

Output

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