[Codeforces Round #842 (Div. 2)] B. Quick Sort

 

 

---

 

※. 올바른 자리에 없는 원소들은 전부 작업을 거쳐야 한다.

(1, 5, 2, 3, 4)

 

※. 올바르지 않은 원소들 중 가장 작은것부터 넣어야 한다.

(1,5,2,3,4 -> 1 - 2 3 - 4 5 작업이 끝나면 정렬 완료)

 

※. 배열을 탐색하며 순서대로 있는 원소는 작업하지 않는다.

(x,1,y,2,z,3 -> 1,2,3 - x y z  1 2 3 은 원소를 뺄 때 정렬)

 

※. n개의 배열 중 순서대로 있는 원소(w)를 뺀 후 작업해야 하는 나머지 원소(n-w)를 k로 나누어 준다.

(+k 는 정렬해야 할 배열이 k개 미만일 때도 최소 1번의 작업을 해야하기 때문에)

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			long ans = 0;
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			LinkedList<Integer> que = new LinkedList<>();
			st = new StringTokenizer(br.readLine()," ");
			int idx = 1;
			for(int i = 0; i < n; i++) {
				que.add(Integer.parseInt(st.nextToken()));
			}
			int cnt = 0;
			while(!que.isEmpty()) {
				int temp = que.poll();
				if(temp == idx) {
					idx++;
				}
			}
			ans = (n-idx+k) / k;
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}
}