Quick Sort (Codeforces 1768B)
Tags: Greedy, math

You are given a permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ and a positive integer $$$k \le n$$$.In one operation, you:   Choose $$$k$$$ distinct elements $$$p_{i_1}, p_{i_2}, \ldots, p_{i_k}$$$.  Remove them and then add them sorted in increasing order to the end of the permutation. For example, if $$$p = [2,5,1,3,4]$$$ and $$$k = 2$$$ and you choose $$$5$$$ and $$$3$$$ as the elements for the operation, then $$$[2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}]$$$.Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven 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: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$).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$$$ is a permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.

Note: In the first test case, the permutation is already sorted.In the second test case, you can choose element $$$3$$$, and the permutation will become sorted as follows: $$$[\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}]$$$.In the third test case, you can choose elements $$$3$$$ and $$$4$$$, and the permutation will become sorted as follows: $$$[1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}]$$$.In the fourth test case, it can be shown that it is impossible to sort the permutation in $$$1$$$ operation. However, if you choose elements $$$2$$$ and $$$1$$$ in the first operation, and choose elements $$$3$$$ and $$$4$$$ in the second operation, the permutation will become sorted as follows: $$$[\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]$$$.

Sample Inputs:
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4

Sample Outputs:
0
1
1
2

Solution (Python):
from collections import *
from math import ceil, gcd, inf
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    (n, k) = map(int, input().split())
    (*arr,) = map(int, input().split())
    l = 1
    for i in arr:
        if i == l:
            l += 1
    print(ceil((n - (l - 1)) / k))

Solution (Python):
from bisect import bisect_right, bisect_left
from math import inf, gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
rvar = lambda : map(int, input().split())
rarr = lambda : list(map(int, input().split()))
rint = lambda : int(input())
import sys
input = sys.stdin.readline
for _ in range(rint()):
    (n, k) = rvar()
    arr = rarr()
    cur = 1
    for i in range(n):
        if cur == arr[i]:
            cur += 1
    print(ceil((n - cur + 1) / k))

Solution (Python):
from bisect import bisect_right, bisect_left
from math import inf, gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
rvar = lambda : map(int, input().split())
rarr = lambda : list(map(int, input().split()))
rint = lambda : int(input())
import sys
input = sys.stdin.readline
for _ in range(rint()):
    (n, k) = rvar()
    arr = rarr()
    cur = 1
    for i in range(n):
        if cur == arr[i]:
            cur += 1
    print(ceil((n - cur + 1) / k))