Min Max Sort (Codeforces 1792C)
Tags: Greedy, two pointers

You are given a permutation $$$p$$$ of length $$$n$$$ (a permutation of length $$$n$$$ is an array of length $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once).You can perform the following operation any number of times (possibly zero):   choose two different elements $$$x$$$ and $$$y$$$ and erase them from the permutation;  insert the minimum of $$$x$$$ and $$$y$$$ into the permutation in such a way that it becomes the first element;  insert the maximum of $$$x$$$ and $$$y$$$ into the permutation in such a way that it becomes the last element. For example, if $$$p = [1, 5, 4, 2, 3]$$$ and we want to apply the operation to the elements $$$3$$$ and $$$5$$$, then after the first step of the operation, the permutation becomes $$$p = [1, 4, 2]$$$; and after we insert the elements, it becomes $$$p = [3, 1, 4, 2, 5]$$$.Your task is to calculate the minimum number of operations described above to sort the permutation $$$p$$$ in ascending order (i. e. transform $$$p$$$ so that $$$p_1 < p_2 < \dots < p_n$$$).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of the test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the permutation.The second line of the test case contains $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ — the given permutation $$$p$$$.The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the minimum number of operations described above to sort the array $$$p$$$ in ascending order.

Note: In the first example, you can proceed as follows:   in the permutation $$$p = [1, 5, 4, 2, 3]$$$, let's choose the elements $$$4$$$ and $$$2$$$, then, after applying the operation, the permutation becomes $$$p = [2, 1, 5, 3, 4]$$$;  in the permutation $$$p = [2, 1, 5, 3, 4]$$$, let's choose the elements $$$1$$$ and $$$5$$$, then, after applying operation, the permutation becomes $$$p = [1, 2, 3, 4, 5]$$$. 

Sample Inputs:
4
5
1 5 4 2 3
3
1 2 3
4
2 1 4 3
6
5 2 4 1 6 3

Sample Outputs:
2
0
1
3

Solution (Python):
def solve():
    n = int(input())
    p = [0] * n
    arr = list(map(int, input().split()))
    for i in range(n):
        x = arr[i]
        x -= 1
        p[x] = i
    l = n // 2
    r = n - l
    while l > 0 and p[l - 1] < p[l] and (p[r] > p[r - 1]):
        l -= 1
        r += 1
    print(l)

def main():
    t = int(input())
    while t > 0:
        solve()
        t -= 1
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import math
import sys
from decimal import Decimal
from math import comb, gcd
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
    return int(input())

def input_list():
    return input().split(' ')

def input_list_int():
    return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
    return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
    global_ans.append(a)

def z_func(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def is_prime(n):
    d = 2
    while n % d != 0:
        d += 1
    return d == n

def partial_sum(a):
    b = [0]
    for i in a:
        b.append(b[-1] ^ i)
    return b

def partial_sum_2d(a):
    n = len(a)
    if n == 0:
        return []
    m = len(a[0])
    b = []
    for i in range(n + 1):
        b.append([0] * (m + 1))
    for i in range(n):
        for j in range(m):
            b[i + 1][j + 1] = a[i][j] + b[i][j + 1] + b[i + 1][j] - b[i][j]
    return b

def dfs(g, v, s, n):
    visited = [0] * (n + 1)

    def dfs_util(v, s):
        if v == s:
            return 1
        if visited[v]:
            return 0
        visited[v] = 1
        for i in g[v]:
            if not visited[i]:
                lr = dfs_util(i, s)
                if lr:
                    return 1
        return 0
    return dfs_util(v, s)

def bs_down(a, x):
    l = -1
    r = len(a)
    while l + 1 < r:
        m = (l + r) // 2
        if a[m] <= x:
            l = m
        else:
            r = m
    return l

def solve():
    n = input_int()
    a = input_list_int()
    if n % 2 == 1:
        ans = n // 2
        mid = n // 2 + 1
        r = mid
        for i in a:
            if i == r:
                r += 1
        l = mid
        for i in reversed(a):
            if i == l:
                l -= 1
        ans -= min(mid - l, r - mid) - 1
        pr(ans)
    else:
        ans = n // 2
        mid1 = n // 2
        mid2 = mid1 + 1
        if a.index(mid1) < a.index(mid2):
            r = mid2
            l = mid1
            for i in a:
                if i == r:
                    r += 1
            for i in reversed(a):
                if i == l:
                    l -= 1
            ans -= min(mid1 - l, r - mid2)
        pr(ans)
query_count = 1
query_count = input_int()
while query_count:
    query_count -= 1
    solve()
for global_ans_line in global_ans:
    if isinstance(global_ans_line, list):
        print(' '.join((str(x) for x in global_ans_line)))
    else:
        print(global_ans_line)

Solution (Python):
for i in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[l[i - 1]] = i - 1
    k = n // 2
    while k > 0 and p[k] < p[k + 1] and (p[n - k] < p[n - k + 1]):
        k -= 1
    print(k)