Description

jbgg 喜欢吃巧克力，这天他找到了找到了一家巧克力商店，商店里有 $n$ 种巧克力。jbgg 从老板那了解到：接下来每一天，老板都会更改其中一种巧克力的价格（价格更改是永久性的）。

jbgg 想知道在每天巧克力价格改变后，在满足选择的巧克力中，价格的最高值与最低值的差小于等于 $k$ 的情况下，最多能买多少种不同的巧克力。

Format

Input

第一行两个整数 $n, k$ $(1 \leqslant n \leqslant 5\times 10^4, 0 \leqslant k \leqslant 10^8)$，分别表示巧克力种数和购买巧克力允许的最大价格差。

第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ $(1 \leqslant a_i \leqslant 10^8)$，$a_i$ 表示从左到右排列的第 $i$ 种巧克力的原始价格。

第三行一个正整数 $q$ $(1 \leqslant q \leqslant 10^5)$，表示天数。

接下来 $q$ 行，每行两个正整数 $p, x$ $(1 \leqslant p \leqslant n, 1 \leqslant x \leqslant 10^8)$，表示将第 $p$ 种巧克力价格更改为 $x$。

Output

应输出 $q$ 行，第 $i$ 行对应第 $i$ 天老板修改完价格后，在满足题意的情况下最多能买到的巧克力种数。

Samples

5 2
2 5 4 3 5
5
3 5
4 99
1 3
4 4
2 7

4
3
4
5
4

Notes

对于给出的样例：

• 第一天，巧克力的价格修改后为 $[2,5,5,3,5]$，jbgg 可以买的巧克力种类为 $\{2,3,4,5\}$，共 $4$ 种;
• 第二天，巧克力的价格修改后为 $[2,5,5,99,5]$，jbgg 可以买的巧克力种类为 $\{2,3,5\}$，共 $3$ 种;
• 第三天，巧克力的价格修改后为 $[3,5,5,99,5]$，jbgg 可以买的巧克力种类为 $\{1,2,3,5\}$，共 $4$ 种;
• 第四天，巧克力的价格修改后为 $[3,5,5,4,5]$，jbgg 可以买的巧克力种类为 $\{1,2,3,4,5\}$，共 $5$ 种;
• 第五天，巧克力的价格修改后为 $[3,7,5,4,5]$，jbgg 可以买的巧克力种类为 $\{1,3,4,5\}$，共 $4$ 种。

Limitation

2s, 512MB for each test case.