長さ$N$の数列$a_1, a_2, ... a_N$の転倒数とは、$1 \leq i < j \leq N$ と$a_i > a_j$を満たす要素の組$(a_i, a_j)$の総数です。
数列の転倒数は、初等的整列アルゴリズムであるバブルソートの交換回数としても知られています。
この問題では、数列中の２つの要素の値を交換し、交換後の数列の転倒数を出力するという操作を行います。
数列と、複数回の操作に関する情報が与えられたとき、各操作の結果を出力するプログラムを作成せよ。ただし、２回目以降の各操作は、その直前の操作の結果得られた数列に対して行うものとする。
入力は以下の形式で与えられる。
$N$ $a_1$ $a_2$ ... $a_N$ $M$ $b_1$ $e_1$ $b_2$ $e_2$ : $b_M$ $e_M$
１行目に数列の要素数$N$ ($2 \leq N \leq 500,000$)が与えられる。２行目に数列の$i$番目の要素の値$a_i$ ($0 \leq a_i \leq 1,000,000,000$) が与えられる。ただし、すべての要素の値は異なる（$i \ne j$ならば$a_i \ne a_j$）。続く行に操作の数$M$ ($1 \leq M \leq 30,000$)が与えられる。続く$M$行に、$i$番目の操作の情報を表す整数の組$b_i$と$e_i$ ($1 \leq b_i < e_i \leq N$)が与えられる。$b_i$と$e_i$は、$i$番目の操作で交換されるのが数列の$b_i$番目と$e_i$番目の要素の値であることを示す。
出力は$M$行である。各操作に対して、操作の結果を１行に出力する。
6 4 6 5 3 1 2 3 2 4 3 6 1 5
9 8 3