Split Sort (Codeforces 1863B)
Tags: Math, sortings

You are given a permutation$$$^{\dagger}$$$ $$$p_1, p_2, \ldots, p_n$$$ of integers $$$1$$$ to $$$n$$$.You can change the current permutation by applying the following operation several (possibly, zero) times:  choose some $$$x$$$ ($$$2 \le x \le n$$$);  create a new permutation by:   first, writing down all elements of $$$p$$$ that are less than $$$x$$$, without changing their order;  second, writing down all elements of $$$p$$$ that are greater than or equal to $$$x$$$, without changing their order;   replace $$$p$$$ with the newly created permutation. For example, if the permutation used to be $$$[6, 4, 3, 5, 2, 1]$$$ and you choose $$$x = 4$$$, then you will first write down $$$[3, 2, 1]$$$, then append this with $$$[6, 4, 5]$$$. So the initial permutation will be replaced by $$$[3, 2, 1, 6, 4, 5]$$$.Find the minimum number of operations you need to achieve $$$p_i = i$$$ for $$$i = 1, 2, \ldots, n$$$. We can show that it is always possible to do so.$$$^{\dagger}$$$ A permutation of length $$$n$$$ 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).

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100\,000$$$).The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$). It is guaranteed that $$$p_1, p_2, \ldots, p_n$$$ is a permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

Output: For each test case, output the answer on a separate line.

Note: In the first test case, $$$n = 1$$$ and $$$p_1 = 1$$$, so there is nothing left to do.In the second test case, we can choose $$$x = 2$$$ and we immediately obtain $$$p_1 = 1$$$, $$$p_2 = 2$$$.In the third test case, we can achieve the minimum number of operations in the following way:  $$$x = 4$$$: $$$[6, 4, 3, 5, 2, 1] \rightarrow [3, 2, 1, 6, 4, 5]$$$;  $$$x = 6$$$: $$$[3, 2, 1, 6, 4, 5] \rightarrow [3, 2, 1, 4, 5, 6]$$$;  $$$x = 3$$$: $$$[3, 2, 1, 4, 5, 6] \rightarrow [2, 1, 3, 4, 5, 6]$$$;  $$$x = 2$$$: $$$[2, 1, 3, 4, 5, 6] \rightarrow [1, 2, 3, 4, 5, 6]$$$. 

Sample Inputs:
5
1
1
2
2 1
6
6 4 3 5 2 1
3
3 1 2
19
10 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13

Sample Outputs:
0
1
4
1
7

Solution (Python):
def main():
    num_test_cases = int(input())
    for _ in range(num_test_cases):
        array_length = int(input())
        array_elements = list(map(int, input().split()))
        element_positions = [0] * (array_length + 1)
        for (position, value) in enumerate(array_elements, start=1):
            element_positions[value] = position
        swaps_required = array_length - 1
        for i in range(2, array_length + 1):
            if element_positions[i] > element_positions[i - 1]:
                swaps_required -= 1
        print(swaps_required)
        print()
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    st = [False] * (n + 10)
    res = 0
    for i in a:
        if i != 1 and st[i - 1] == False:
            res += 1
        st[i] = True
    print(res)
for i in range(int(input().strip())):
    solve()

Solution (Python):
def solve():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    st = [False] * (n + 10)
    res = 0
    for i in a:
        if i != 1 and st[i - 1] == False:
            res += 1
        st[i] = True
    print(res)
for i in range(int(input().strip())):
    solve()