Permutation Graph (Codeforces 1696D)
Tags: Greedy, divide and conquer

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).You are given a permutation of $$$1,2,\dots,n$$$, $$$[a_1,a_2,\dots,a_n]$$$. For integers $$$i$$$, $$$j$$$ such that $$$1\le i<j\le n$$$, define $$$\operatorname{mn}(i,j)$$$ as $$$\min\limits_{k=i}^j a_k$$$, and define $$$\operatorname{mx}(i,j)$$$ as $$$\max\limits_{k=i}^j a_k$$$.Let us build an undirected graph of $$$n$$$ vertices, numbered $$$1$$$ to $$$n$$$. For every pair of integers $$$1\le i<j\le n$$$, if $$$\operatorname{mn}(i,j)=a_i$$$ and $$$\operatorname{mx}(i,j)=a_j$$$ both holds, or $$$\operatorname{mn}(i,j)=a_j$$$ and $$$\operatorname{mx}(i,j)=a_i$$$ both holds, add an undirected edge of length $$$1$$$ between vertices $$$i$$$ and $$$j$$$.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$$$, $$$\ldots$$$, $$$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$$$.

Note: The following are illustrations of constructed graphs in example test cases.  the constructed graph in test case 1   the constructed graph in test case 2   the constructed graph in test case 3   the constructed graph in test case 4   the constructed graph in test case 5 

Sample Inputs:
5
1
1
2
1 2
5
1 4 2 3 5
5
2 1 5 3 4
10
7 4 8 1 6 10 3 5 2 9

Sample Outputs:
0
1
1
4
6

Solution (Python):
import os, sys
from io import BytesIO, IOBase

def solve(n, a):
    if n == 1:
        print(0)
        return
    max_ = [-1] * n
    (cur_mx, idx) = (-float('inf'), -1)
    for i in range(n - 1, -1, -1):
        if a[i] > cur_mx:
            (idx, cur_mx) = (i, a[i])
        max_[i] = idx
    min_ = [-1] * n
    (cur_mn, idx) = (float('inf'), -1)
    for i in range(n - 1, -1, -1):
        if a[i] < cur_mn:
            (idx, cur_mn) = (i, a[i])
        min_[i] = idx
    cur = 0
    res = 0
    right = 1
    while cur != n - 1:
        res += 1
        if cur == max_[cur]:
            cur = min_[cur]
        elif cur == min_[cur]:
            cur = max_[cur]
        else:
            next_ = cur + 1
            if a[next_] > a[cur]:
                while a[right] > a[cur]:
                    if a[right] > a[next_]:
                        next_ = right
                    right += 1
                cur = next_
            else:
                while a[right] < a[cur]:
                    if a[right] < a[next_]:
                        next_ = right
                    right += 1
                cur = next_
    print(res)

def main():
    for _ in range(int(input())):
        n = int(input())
        a = list(map(lambda x: int(x) - 1, input().split(' ')))
        solve(n, a)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    k = [None] * n
    for (i, x) in enumerate(map(int, input().split())):
        k[x - 1] = i
    count = 0
    (i, j, d) = (0, n - 1, k[0])
    while d != 0:
        while k[j] > d:
            j -= 1
        d = k[j]
        count += 1
        if d == 0:
            break
        while k[i] > d:
            i += 1
        d = k[i]
        count += 1
    (i, j, d) = (0, n - 1, k[0])
    while d != n - 1:
        while k[j] < d:
            j -= 1
        d = k[j]
        count += 1
        if d == n - 1:
            break
        while k[i] < d:
            i += 1
        d = k[i]
        count += 1
    print(count)

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    a = list(map(int, inp().split()))
    pos = [None] * (n + 1)
    for i in range(n):
        pos[a[i]] = i
    st1 = [(-1, n)]
    st2 = [(n + 1, n)]
    next_below = [None] * n
    next_above = [None] * n
    for i in range(n - 1, -1, -1):
        v = a[i]
        while st1[-1][0] > v:
            st1.pop()
        next_below[i] = st1[-1][1]
        st1.append((v, i))
        while st2[-1][0] < v:
            st2.pop()
        next_above[i] = st2[-1][1]
        st2.append((v, i))
    i = 0
    ans = 0
    while i + 1 < n:
        v = a[i]
        if v < a[i + 1]:
            next = next_below[i]
            j = next_above[i]
            while next_above[j] < next:
                j = next_above[j]
        else:
            next = next_above[i]
            j = next_below[i]
            while next_below[j] < next:
                j = next_below[j]
        i = j
        ans += 1
    print(ans)

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()