AT_aalc001_t K-転倒数

正整数 $ K $ と、長さ $ L $ の整数列 $ C=(C_1,C_2,\ldots,C_L) $ に対し、 $ C $ の **$ K $ -転倒数** を、以下の条件をともに満たす整数の組 $ (i,j) $ の個数として定義します。 - $ 1 \le i \lt j \le L $ - $ C_j \lt C_i \le C_j+K $ 正整数 $ N,Q,K $ と、長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。 $ i $ 番目のクエリでは、正整数 $ m_i,x_i $ が与えられます。 $ t $ を $ 0 $ 以上 $ m_i $ 以下の整数から選び、数列 $ (A_1,A_2,\ldots,A_{m_i}) $ の先頭から $ t $ 個の要素の直後に $ x_i $ を挿入します。すなわち、挿入後の数列は \\\[ (A\_1,\\ldots,A\_t,x\_i,A\_{t+1},\\ldots,A\_{m\_i}) \\\] となります。ただし、 $ t=0 $ のときは先頭に、 $ t=m_i $ のときは末尾に $ x_i $ を挿入するものとします。 挿入後の数列の $ K $ -転倒数としてあり得る最小値を求めてください。なお、それぞれのクエリは独立です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ m_1 $ $ x_1 $ $ m_2 $ $ x_2 $ $ \vdots $ $ m_Q $ $ x_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて、 $ t=0 $ として $ 2 $ を挿入すると、数列は $ (2,3,1,4,2) $ となり、その $ 2 $ -転倒数は $ 4 $ です。 $ 2 $ -転倒数を $ 3 $ 以下にする挿入位置は存在しないため、答えは $ 4 $ です。 ### Constraints - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 1 \le K \le N $ - $ 1 \le A_i \le N $ - $ 1 \le m_i \le N $ - $ 1 \le x_i \le N $ - 入力される数値はすべて整数