Minimum Swap Sorting in Queue

In a class there are \(N\) students with IDs ranging from \(0\) to \(N-1\). In one lesson, the teacher calls \(M\) students one by one to join a queue. Initially the queue is empty. When a student is called, he/she first takes a position at the end of the queue. Then, all students in the queue rearrange themselves into ascending order according to their heights by performing a series of swap operations (each swap operation exchanges the positions of any two students). Note that if two students have the same height, any order among them is acceptable. In this problem, you may assume that all heights are distinct.

Your task is: after each new student joins the queue, compute the minimum number of swaps required to transform the current order of the queue into the order sorted in ascending order.

For example, if the current queue has 4 students with heights: 10, 17, 3, 25, then after the student with height 3 joins (making the order [10, 17, 3]), the sorted order should be [3, 10, 17]. One way to achieve this is to swap student 10 with student 3, and we find that the minimum number of swaps needed is 2; after the fourth student (height 25) joins, the order becomes [10, 17, 3, 25] which, when sorted, should be [3, 10, 17, 25]—again requiring 2 swaps.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le M \le N \le 10^5\)). Here, \(N\) is the total number of students in the class (their IDs range from 0 to \(N-1\)) and \(M\) is the number of students called by the teacher.

The second line contains \(M\) space-separated integers, where each integer represents the height of a student in the order they are called to join the queue.

outputFormat

Output \(M\) lines. The \(i\)-th line should contain a single integer representing the minimum number of swaps required for the queue (formed by the first \(i\) called students) to be arranged in ascending order.

sample

4 4
10 17 3 25

0
0
2
2