Перестановкой является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Дана перестановка $$$[a_1,a_2,\dots,a_n]$$$ чисел $$$1,2,\dots,n$$$. Для целых $$$i$$$,$$$j$$$, таких что $$$1\le i<j\le n$$$, определим $$$\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<j\le n$$$, если одновременно $$$\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$$$ всегда будут соединены каким-либо путём, так что кратчайший путь всегда существует.