Counting Inversions After Each Swap

A group of kindergarten kids are lined up to eat fruits. However, due to different heights, the lineup looks messy. For each kid, let h_i denote the height of the i-th kid. Initially, you are given the sequence of heights and you need to calculate the number of inversion pairs in this sequence. An inversion pair is defined as a pair of indices (i, j) such that i < j and h_i > h_j (in latex: \(i h_j\)).

After the initial count, a teacher performs several swap operations. In each operation, two kids (at given positions) swap places. After each swap, you must output the updated number of inversion pairs of the new sequence.

Input Specification:

• The first line contains two integers n and m indicating the number of kids and the number of swap operations, respectively.
• The second line contains n integers h₁ h₂ ... h_n representing the heights.
• The following m lines each contain two integers i and j (1-indexed) indicating the positions of the kids to swap.

Output Specification:

• Output m+1 lines. The first line is the inversion count of the initial sequence, and each of the following m lines is the inversion count after each corresponding swap.

inputFormat

The input begins with a line containing two integers n and m. The next line contains n space-separated integers representing the kids' heights. This is followed by m lines, each containing two space-separated integers representing the positions of the kids to swap.

outputFormat

Output m+1 lines. The first line should contain the inversion count of the initial sequence. Each subsequent line should contain the inversion count after each swap operation.

sample

5 3
3 1 4 5 2
1 2
3 5
2 4

4
3
2
3