Bubble Sort Scan Count Query

This problem involves the classic bubble sort algorithm. You are given a sequence \(A_0, A_1, \ldots, A_{N-1}\). In one scan (pass) of the sequence, for each index \(i=0,1,\ldots,N-2\) in order, if \(A_i > A_{i+1}\) then the two elements are swapped. It is well known that after a finite number of scans the sequence becomes sorted in non-decreasing order.

For a given sequence \(A\), we define the bubble sort scan count as the number of scans performed until the sequence is sorted. One can prove that this count is equal to

[ \max_{0\le i\le N-1}{ (i - \text{pos}(i)) } + 1, ]

where for each index \(i\), \(\text{pos}(i)\) is the position of \(A_i\) in the stable sorted order of the sequence (i.e. when sorting by value, if two elements are equal then the one with a smaller original index comes first). In other words, each element can move at most one position to the left per scan. Thus if an element is \(k\) positions to the right of its correct (stable sorted) position, then at least \(k+1\) scans are required.

You are given an initial sequence of length \(N\) and then \(Q\) queries. In the \((j+1)\)th query (\(0 \le j \le Q-1\)), the value of \(A_{X_j}\) is changed to \(V_j\). After each modification you are to determine the bubble sort scan count of the updated sequence.

Input and Output Formats: See the input/output descriptions below.

inputFormat

The first line contains two integers \(N\) and \(Q\) --- the length of the sequence and the number of queries.

The second line contains \(N\) integers \(A_0, A_1, \ldots, A_{N-1}\) representing the initial sequence.

Then, \(Q\) lines follow. The \(j\)th of these lines contains two integers \(X_j\) and \(V_j\) indicating that the value at index \(X_j\) (0-indexed) of the sequence is updated to \(V_j\).

outputFormat

Output \(Q\) lines. On the \(j\)th line, output the bubble sort scan count after performing the \(j\)th update.

sample

3 3
2 3 1
1 1
2 2
0 3

2
2
2