AT_aalc001_t.K-Inversion Count

对于正整数 $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$。

选择一个介于 $0$ 与 $m_i$（含端点）之间的整数 $t$，并将 $x_i$ 插入到序列 $(A_1,A_2,\ldots,A_{m_i})$ 的前 $t$ 个元素之后。即，得到的新序列为

\[ (A_1,\ldots,A_t,x_i,A_{t+1},\ldots,A_{m_i}) \]

其中，若 $t=0$，则 $x_i$ 插入到开头；若 $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$ 个查询的答案。

样例 1 解释：
对于第 $1$ 个查询，将 $2$ 在时刻 $t=0$ 插入，得到序列 $(2,3,1,4,2)$，其 $2$-逆序对数为 $4$。不存在任何插入位置能使 $2$-逆序对数不超过 $3$，因此答案为 $4$。

约束条件

• $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$
• 输入中的所有数值均为整数。