AT_aalc001_t K-転倒数

For a positive integer $ K $ and a sequence of integers $ C=(C_1,C_2,\ldots,C_L) $ of length $ L $ , define the **$ K $ -inversion count** of $ C $ as the number of pairs of integers $ (i,j) $ satisfying both of the following conditions: - $ 1 \le i \lt j \le L $ - $ C_j \lt C_i \le C_j+K $ You are given positive integers $ N,Q,K $ and a sequence of nonnegative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Process $ Q $ queries. In the $ i $ -th query, you are given positive integers $ m_i,x_i $ . Choose an integer $ t $ between $ 0 $ and $ m_i $ , inclusive, and insert $ x_i $ immediately after the first $ t $ elements of the sequence $ (A_1,A_2,\ldots,A_{m_i}) $ . That is, the resulting sequence is \\\[ (A\_1,\\ldots,A\_t,x\_i,A\_{t+1},\\ldots,A\_{m\_i}) \\\] Here, $ x_i $ is inserted at the beginning if $ t=0 $ , and at the end if $ t=m_i $ . Find the minimum possible $ K $ -inversion count of the resulting sequence. Each query is independent.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ m_1 $ $ x_1 $ $ m_2 $ $ x_2 $ $ \vdots $ $ m_Q $ $ x_Q $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 For query $ 1 $ , inserting $ 2 $ with $ t=0 $ gives the sequence $ (2,3,1,4,2) $ , whose $ 2 $ -inversion count is $ 4 $ . There is no insertion position that makes the $ 2 $ -inversion count at most $ 3 $ , so the answer is $ 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 $ - All numerical values in the input are integers.