Read problem statements in [Russian], [Mandarin] and [Vietnamese] as well.

You are given a permutation P of integers from 1 to N, and an integer K such that \lceil \frac{2N}{3}\rceil ≤ K ≤ N. In one operation, you can do the following:

Choose any consecutive segment of at most K elements of the permutation, and sort it in increasing order.

What's the smallest number of operations you have to make to sort the entire permutation in increasing order?

------ Input Format ------ 

- The first line of the input contains a single integer T  - the number of test cases. The description of test cases follows.

- The first line of each test case contains two integers N, K.

- The second line of each test case contains N integers P_{1}, P_{2}, \ldots, P_{N} - the elements of the permutation.

------ Output Format ------ 

For each test case, output the smallest number of operations you have to make to sort the entire permutation in increasing order.

------ Constraints ------ 

$1 ≤T ≤10^{4}$
$3 ≤N ≤2\cdot 10^{5}$
$\lceil \frac{2N}{3}\rceil ≤K ≤N$
$1 ≤P_{i} ≤N$
$P_{i} \neq P_{j}$ for $i\neq j$
- The sum of $N$ over all test cases doesn't exceed $10^{6}$.

----- Sample Input 1 ------ 
4
6 4
1 2 3 4 5 6
6 4
1 2 4 3 5 6
6 4
6 5 2 1 4 3
6 4
2 6 4 3 1 5

----- Sample Output 1 ------ 
0
1
2
3

----- explanation 1 ------ 
In the first test case, the permutation is already sorted.

In the second test case, you can choose segment $P[3:4]$ and sort it. The permutation will then be sorted.

In the third test case, you can sort segment $P[1:4]$ first, getting $(1, 2, 5, 6, 4, 3)$, and then $P[3:6]$.

In the fourth test case, you can sort segments in the order: $P[2:5]$, getting $(2, 1, 3, 4, 6, 5)$, then $P[1:2]$, getting $(1, 2, 3, 4, 6, 5)$, then $P[5:6]$, getting $(1, 2, 3, 4, 5, 6)$.

Difficulty: HARD
Tags: Sorting

Constructive algorithms

Implementation

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sorted_arr = sorted(arr)
	if arr == sorted_arr:
		print(0)
		continue
	(index_x, index_y) = (0, 0)
	for i in range(n):
		if arr[i] == i + 1:
			index_x += 1
		else:
			break
	for i in reversed(range(n)):
		if arr[i] == i + 1:
			index_y += 1
		else:
			break
	if n - index_x - index_y <= k:
		print(1)
		continue
	index_y = min(n - index_y - k, n)
	temp1 = arr[0:index_x] + sorted(arr[index_x:index_x + k]) + arr[index_x + k:n]
	arr1 = temp1[0:index_y] + sorted(temp1[index_y:index_y + k]) + temp1[index_y + k:n]
	temp2 = arr[0:index_y] + sorted(arr[index_y:index_y + k]) + arr[index_y + k:n]
	arr2 = temp1[0:index_x] + sorted(temp2[index_x:index_x + k]) + temp2[index_x + k:n]
	print(2) if arr1 == sorted_arr or arr2 == sorted_arr else print(3)


import sys
i = iter(([*map(int, s.split())] for s in sys.stdin))
next(i)
for ((n, k), a) in zip(i, i):
	b = ''.join(('01'[i == j] for (i, j) in zip(range(1, n + 1), a)))
	l = b.find('0')
	if l < 0:
		ans = 0
	else:
		r = b.rfind('0') + 1
		m = r - l
		if m <= k:
			ans = 1
		else:
			(*t,) = range(l + 1, r + 1)
			(i, j) = (0, k)
			for u in range(4):
				if ~u & 1:
					b = a[l:r]
				b[i:j] = sorted(b[i:j])
				if u & 1:
					if b == t:
						ans = 2
						break
				else:
					(i, j) = (m - j, m - i)
			else:
				ans = 3
	print(ans)


def sort(a, i, j):
	d = []
	for l in range(i, j):
		d.append(a[l])
	d.sort()
	x = 0
	for l in range(i, j):
		a[l] = d[x]
		x += 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [i + 1 for i in range(n)]
	a1 = a.copy()
	c = 0
	if a == b:
		print(0)
		continue
	while a != b:
		c += 1
		if c == 2:
			break
		element = -1
		for i in range(n):
			if i + 1 != a[i]:
				left = i
				element = i + 1
				break
		right = a.index(element)
		rem = right - left + 1
		if rem >= k:
			sort(a, max(0, right - k + 1), right + 1)
		else:
			sort(a, left, min(n, left + k))
	if c == 1:
		print(c)
		continue
	a = a1.copy()
	left = 0
	for i in range(n):
		if a[i] != i + 1:
			left = i
			break
	right = n
	for i in range(n - 1, -1, -1):
		if a[i] != i + 1:
			right = i + 1
			break
	a1 = a.copy()
	a2 = a.copy()
	sort(a1, left, min(right, left + k))
	pos = left
	for i in range(n):
		if a1[i] != i + 1:
			left = i
			break
	for i in range(n - 1, -1, -1):
		if a1[i] != i + 1:
			right = i + 1
			break
	sort(a1, left, min(right, left + k))
	if a1 == b:
		print(2)
		continue
	for i in range(n):
		if a[i] != i + 1:
			left = i
			break
	for i in range(n - 1, -1, -1):
		if a[i] != i + 1:
			right = i + 1
			break
	sort(a2, max(left, right - k), right)
	sort(a2, left, min(right, left + k))
	if a2 == b:
		print(2)
		continue
	print(3)


import copy
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	arr = [int(i) for i in input().strip().split()]
	shifts = [abs(k - (index + 1)) for (index, k) in enumerate(arr)]
	if sum(shifts) == 0:
		print(0)
		continue
	index_left = 0
	index_right = n - 1
	while shifts[index_left] == 0:
		index_left += 1
	while shifts[index_right] == 0:
		index_right -= 1
	if index_right - index_left + 1 <= k:
		print(1)
		continue
	copy_1 = arr[:]
	copy_2 = arr[:]
	copy_1[index_left:min(n - 1, k + index_left)] = sorted(copy_1[index_left:min(n - 1, k + index_left)])
	copy_1[max(0, index_right - k + 1):index_right + 1] = sorted(copy_1[max(0, index_right - k + 1):index_right + 1])
	copy_2[max(0, index_right - k + 1):index_right + 1] = sorted(copy_2[max(0, index_right - k + 1):index_right + 1])
	copy_2[index_left:min(n - 1, k + index_left)] = sorted(copy_2[index_left:min(n - 1, k + index_left)])
	flag_1 = 0
	flag_2 = 0
	for (index, z) in enumerate(copy_1):
		if index != z - 1:
			flag_1 = 1
			break
	for (index, z) in enumerate(copy_2):
		if index != z - 1:
			flag_2 = 1
			break
	if flag_1 and flag_2:
		print(3)
	else:
		print(2)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
inp = lambda : int(stdin.readline())
strng = lambda : stdin.readline().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(stdin.readline().strip())
mul = lambda : map(int, stdin.readline().strip().split())
mulf = lambda : map(float, stdin.readline().strip().split())
seq = lambda : list(map(int, stdin.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def sol(l, k):
	(c1, c2) = (0, 0)
	for i in range(n):
		if l[i] == i + 1:
			c1 += 1
		else:
			break
	for i in range(n - 1, -1, -1):
		if l[i] == i + 1:
			c2 += 1
		else:
			break
	if c1 == n:
		return 0
	if n - c1 - c2 <= k:
		return 1
	t = l[c1:n - c2]
	ts = sorted(t)
	t1 = sorted(t[:k]) + t[k:]
	t1 = t1[:len(t) - k] + sorted(t1[len(t) - k:])
	t2 = t[:len(t) - k] + sorted(t[len(t) - k:])
	t2 = sorted(t2[:k]) + t2[k:]
	if t1 == ts or t2 == ts:
		return 2
	else:
		return 3
for _ in range(int(input())):
	(n, k) = mul()
	l = seq()
	print(sol(l, k))


def ans1(n, k, arr):
	count = 0
	for i in range(n):
		if arr[i] != i + 1:
			right = min(i + k, n)
			arr = arr[0:i] + sorted(arr[i:right]) + arr[right:n]
			count += 1
			break
	for i in reversed(range(n)):
		if arr[i] != i + 1:
			left = max(i - k + 1, 0)
			arr = arr[0:left] + sorted(arr[left:i + 1]) + arr[i + 1:n]
			count += 1
			break
	for i in range(n):
		if arr[i] != i + 1:
			count += 1
			break
	return count

def ans2(n, k, arr):
	count = 0
	for i in reversed(range(n)):
		if arr[i] != i + 1:
			left = max(i - k + 1, 0)
			arr = arr[0:left] + sorted(arr[left:i + 1]) + arr[i + 1:n]
			count += 1
			break
	for i in range(n):
		if arr[i] != i + 1:
			right = min(i + k, n)
			arr = arr[0:i] + sorted(arr[i:right]) + arr[right:n]
			count += 1
			break
	for i in range(n):
		if arr[i] != i + 1:
			count += 1
			break
	return count
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	print(min(ans1(n, k, arr), ans2(n, k, arr)))
	t = t - 1


try:

	def solve(A, K):
		A[:K] = sorted(A[:K])
		A[len(A) - K:] = sorted(A[len(A) - K:])
		return A

	def solveReverse(A, K):
		A[len(A) - K:] = sorted(A[len(A) - K:])
		A[:K] = sorted(A[:K])
		return A

	def isSorted(A):
		temp = list(A)
		temp.sort()
		if A == temp:
			return True
		return False
	for t in range(int(input())):
		(N, K) = map(int, input().split())
		P = list(map(int, input().split()))
		if isSorted(P):
			print(0)
			continue
		L = 0
		R = N - 1
		while P[L] == L + 1:
			L += 1
		while P[R] == R + 1:
			R -= 1
		if R - L + 1 <= K:
			print(1)
			continue
		if isSorted(solve(P[L:R + 1], K)) or isSorted(solveReverse(P[L:R + 1], K)):
			print(2)
			continue
		print(3)
except:
	pass


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()
	a = L()
	f = 0
	for i in range(n):
		if a[i] != i + 1:
			f = 1
			break
	if f == 0:
		print(0)
		continue
	i = 0
	j = n - 1
	while i < n:
		if a[i] != i + 1:
			break
		i += 1
	while j >= 0:
		if a[j] != j + 1:
			break
		j -= 1
	if j - i + 1 <= k:
		print(1)
		continue
	b = a[:]
	a = sorted(a[:min(i + k, n)]) + a[min(i + k, n):]
	a = a[:max(j - k + 1, 0)] + sorted(a[max(0, j - k + 1, 0):])
	b = b[:max(j - k + 1, 0)] + sorted(b[max(0, j - k + 1, 0):])
	b = sorted(b[:min(i + k, n)]) + b[min(i + k, n):]
	f1 = f2 = 0
	for i in range(n):
		if a[i] != i + 1:
			f1 = 1
		if b[i] != i + 1:
			f2 = 1
	if f1 == 0 or f2 == 0:
		print(2)
		continue
	else:
		print(3)


from math import ceil
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = sorted(a)
	if a == b:
		print(0)
	else:
		(f, l) = (-1, -1)
		for j in range(n):
			if a[j] != b[j]:
				if f == -1:
					f = j
				l = j
		seg = l - f + 1
		if seg <= k:
			print(1)
		else:
			c = a.copy()
			x = a[f:f + k]
			x.sort()
			a[f:f + k] = x
			x = a[l - k + 1:l + 1]
			x.sort()
			a[l - k + 1:l + 1] = x
			x = c[l - k + 1:l + 1]
			x.sort()
			c[l - k + 1:l + 1] = x
			x = c[f:f + k]
			x.sort()
			c[f:f + k] = x
			if a == b or c == b:
				print(2)
			else:
				print(3)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = 0
	for i in range(n - 1, -1, -1):
		if a[i] != i + 1:
			mx = i + 1
			break
	a = a[:mx]
	n = len(a)
	mn = n
	for i in range(n):
		if a[i] != i + 1:
			mn = i
			break
	a = a[mn:]
	n = len(a)
	for i in range(n):
		a[i] = a[i] - mn
	if n == 0:
		print(0)
	elif n <= k:
		print(1)
	else:
		f1 = 0
		f2 = 0
		f3 = 0
		l1 = 0
		l2 = 0
		l3 = 0
		s1 = 0
		s2 = 0
		s3 = 0
		for i in range(n - k):
			if a[i] <= n - k:
				f1 += 1
			elif n - k < a[i] <= k:
				f2 += 1
			else:
				f3 += 1
		for i in range(n - k, k):
			if a[i] <= n - k:
				s1 += 1
			elif n - k < a[i] <= k:
				s2 += 1
			else:
				s3 += 1
		for i in range(k, n):
			if a[i] <= n - k:
				l1 += 1
			elif n - k < a[i] <= k:
				l2 += 1
			else:
				l3 += 1
		if l1:
			if f3:
				print(3)
			else:
				print(2)
		elif s1:
			if f3:
				print(2)
			else:
				p = 0
				for i in range(k, n):
					if a[i] != i + 1:
						p = 1
						break
				if p == 0:
					print(1)
				else:
					print(2)
		elif l2:
			p = 0
			for i in range(n - k):
				if a[i] != i + 1:
					p = 1
					break
			if p == 0:
				print(1)
			else:
				print(2)
		else:
			fi = 1
			se = 1
			th = 1
			for i in range(n - k):
				if a[i] != i + 1:
					fi = 0
					break
			for i in range(n - k, k):
				if a[i] != i + 1:
					se = 0
					break
			for i in range(k, n):
				if a[i] != i + 1:
					th = 0
					break
			if fi == 0 and se == 0 and (th == 0) or (fi == 0 and se == 1 and (th == 0)):
				print(2)
			elif fi == 1 and se == 1 and (th == 1):
				print(0)
			else:
				print(1)


from sys import stdin
input = stdin.readline

def zero():
	if a == sorted(a):
		return True
	return False

def one(a):
	front = 0
	for i in range(n - k):
		if a[i] == i + 1:
			front += 1
		else:
			break
	back = 0
	for i in range(n - k):
		if a[n - i - 1] == n - i:
			back += 1
		else:
			break
	total = front + back
	if n - total <= k:
		return True
	return False

def two():
	a_dup = a[:]
	for i in range(n):
		if a[i] != i + 1:
			start = i
			break
	x = []
	for i in range(start, start + k):
		x.append(a[i])
	x.sort()
	for i in range(start, start + k):
		a_dup[i] = x[i - start]
	if one(a_dup):
		return True
	a_dup = a[:]
	for i in range(n - 1, -1, -1):
		if a[i] != i + 1:
			start = i
			break
	x = []
	for i in range(start, start - k, -1):
		x.append(a[i])
	x.sort(reverse=True)
	for i in range(start, start - k, -1):
		a_dup[i] = x[start - i]
	if one(a_dup):
		return True
	return False

def answer():
	if zero():
		return 0
	if one(a):
		return 1
	if two():
		return 2
	return 3
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


import sys
import bisect as bi
from collections import defaultdict as dd
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))

def ans(ar, k, st, en):
	n = len(ar)
	if k >= n:
		return 1 - (sorted(ar) == ar)
	an = 0
	for i in range(k, n):
		if ar[i] <= st + n - k - 1:
			ar = ar[:n - k] + sorted(ar[n - k:])
			ar = sorted(ar[:k]) + ar[k:]
			an += 2
			break
	else:
		an += 1
		ar = sorted(ar[:k]) + ar[k:]
	return an + 1 - (sorted(ar) == ar)
(t,) = I()
for i in range(t):
	(n, k) = I()
	l = I()
	i = 0
	j = n - 1
	while i < n and l[i] == i + 1:
		i += 1
	while j >= 0 and l[j] == j + 1:
		j -= 1
	an = ans(l[i:j + 1], k, i + 1, j + 1)
	print(an)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split(' '))
	P = list(map(int, input().split(' ')))
	for alpha in range(N):
		P[alpha] -= 1
	while N != 0 and P[-1] == N - 1:
		del P[-1]
		N -= 1
	tc = 0
	while N != 0 and P[0] == tc:
		del P[0]
		N -= 1
		tc += 1
	for gamma in range(N):
		P[gamma] -= tc
	if N == 0:
		print(0)
	elif K >= N:
		print(1)
	else:
		b = []
		for theta in range(N):
			b.append(P[theta])
		ideal = [j for j in range(N)]
		P[:K] = sorted(P[:K])
		P[N - K:] = sorted(P[N - K:])
		b[N - K:] = sorted(b[N - K:])
		b[:K] = sorted(b[:K])
		if P == ideal or b == ideal:
			print(2)
		else:
			print(3)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		a[i] -= 1
		d[a[i]] = i
	b = sorted(a)
	l = -1
	for i in range(n):
		if a[i] != i:
			l = i
			break
	r = -1
	for i in range(n - 1, -1, -1):
		if a[i] != i:
			r = i
			break
	if l == -1 or r == -1:
		print(0)
		continue
	if r - l + 1 <= k:
		print(1)
		continue
	c = a.copy()
	d = a.copy()
	c[l:l + k] = sorted(c[l:l + k])
	if c == b:
		print(1)
		continue
	c[r - k + 1:r + 1] = sorted(c[r - k + 1:r + 1])
	if c == b:
		print(2)
		continue
	d[r - k + 1:r + 1] = sorted(d[r - k + 1:r + 1])
	if d == b:
		print(1)
		continue
	d[l:l + k] = sorted(d[l:l + k])
	if d == b:
		print(2)
		continue
	print(3)