Codeforces: Permutation Graph

We are given a permutation of $1,2,...,n$, $a_1, a_2, ..., a_n$. Construct the undirected graph with vertex set $1, 2, ..., n$ and $(i, j)$ an edge iff $\min_{k=i}\{a_k\}=a_i$ and $\max_{k=i}\{a_k\}=a_j$ or the reverse. Find the shortest path from vertex $1$ to $n$. Here $n\leq 2.5\times 10^5$.

The main idea:

Firstly, we observe that a $(1,n)$-path always exists since for any vertices $i$ and $i+1$ we have the edge $(i,i+1)$.

Consider the element with value $1$, say it is at position $i$. Similarly, the element with value $n$ at position, say $j$.

$$a_1, ..., a_i, ..., a_j, ..., a_n$$

We have the edge $(i, j)$. Additionally, there can be no edge $(x,y)$ with $x<i$ and $y>i$ or $x < j$ and $y>j$. Therefore, the shortest path must take the edge $(i,j)$, and we can apply a divide-and-conquer strategy on the sub-arrays $a_1, ..., a_{i-1}$ and $a_{j+1}, ..., a_n$. This can be implemented in linear time.