1461 - 交換と転倒数

問題文

長さ $N$ の数列 $a_{1}, a_{2}, \cdots ,a_{N}$の転倒数とは、$1 \leq i \lt j \leq N$ と $a_{i} \gt a_{j}$を満たす要素の組$(a_{i}, a_{j})$の総数です。 数列の転倒数は、初等的整列アルゴリズムであるバブルソートの交換回数としても知られています。 この問題では、数列中の$2$つの要素の値を交換し、交換後の数列の転倒数を出力するという操作を行います。

課題

数列と、複数回の操作に関する情報が与えられたとき、各操作の結果を出力するプログラムを作成せよ。 ただし、$2$回目以降の各操作は、その直前の操作の結果得られた数列に対して行うものとする。

入力

入力は以下の形式で与えられる。

$N \  M$
$u_{1} \  v_{1} \  c_{1}$
$u_{2} \  v_{2} \  c_{2}$
$\vdots$
$u_{M} \  v_{M} \  c_{M}$

$1$行目に数列の要素数$N \ (2 \leq N \leq 500,000)$が与えられる。$2$行目に数列の$i$番目の要素の値$a_{i} \ (0 \leq a_{i} \leq 1,000,000,000)$が与えられる。ただし、すべての要素の値は異なる$(i \neq j$ならば$a_{i} \neq a_{j})$。 続く行に操作の数$M \ (1 \leq M \leq 30,000)$が与えられる。続く$M$行に、$i$番目の操作の情報を表す整数の組$b_{i}$と$e_{i} \ (1 \leq b_{i} \lt e_{i} \leq N)$が与えられる。 $b_{i}$と$e_{i}$は、$i$番目の操作で交換されるのが数列の$b_{i}$番目と$e_{i}$番目の要素の値であることを示す。
入力に対して、実行時間が$8$秒を超えてはならない。

出力

出力は $M$ 行である。各操作に対して、操作の結果を$1$行に出力する。

入出力例

入力例1

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

出力例1

9
8
3