Перестановкой является массив, состоящий из \(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\) всегда будут соединены каким-либо путём, так что кратчайший путь всегда существует.