Distinct Inversion Pairs with Updates

You are given a sequence \(a\) of \(n\) integers. A pair \((i, j)\) (with \(i < j\)) is called an inversion pair if \(a_i > a_j\). Two inversion pairs \((i_1, j_1)\) and \((i_2, j_2)\) are considered essentially different if and only if \(a_{i_1} \neq a_{i_2}\) or \(a_{j_1} \neq a_{j_2}\) (i.e. they differ in at least one of the two values).

The task is twofold:

1. Initially count the number of essentially different inversion pairs in the sequence.
2. Then, there are \(q\) modifications. Each modification is given as two integers \(x\) and \(y\), meaning that the element at index \(x\) (1-indexed) is updated to \(y\). Note: These modifications are sequential i.e. each update affects the subsequent ones.

After each modification, output the count of essentially different inversion pairs for the current sequence.

Formally, for a sequence \(a\), an inversion pair is defined as:

[ (i,j) \text{ is an inversion pair if and only if } i < j \text{ and } a_i > a_j, ]

Two inversion pairs \((i_1, j_1)\) and \((i_2, j_2)\) are essentially different if:

[ a_{i_1} \neq a_{i_2} \quad \text{or} \quad a_{j_1} \neq a_{j_2}. ]

You need to output the number of essentially different inversion pairs after each update.

Note: Various subtasks in this problem have different time and memory constraints, encouraging different solution techniques.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of elements in the sequence and the number of modifications, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial sequence.

Each of the next \(q\) lines contains two integers \(x\) and \(y\) representing a modification: update the element at position \(x\) (1-indexed) to \(y\).

outputFormat

For each modification, output a single line containing the number of essentially different inversion pairs in the sequence after the update.

sample

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

5
4
4

</p>