题目描述

有 n 个数字 $a_1, a_2, ..., a_n$，在一个团体里，按照 1,2,...,n 标号，它们会相互竞争。一个数字不会与团体里的其他数字竞争。当它们不竞争对于时就会输。它总共要进行 $n - 1$ 次竞争，如果它输掉至少 $\left\lfloor \frac{n-1}{2} \right\rfloor$ 次竞赛，就会因此感到麻木。请注意，「向上取整」是 $\left\lfloor \frac{n-1}{2} \right\rfloor$ 的最大整数。

因此，每天会给一些数字写以感到麻木。作为一位善良的心理治疗师，你认为有必要和它们谈谈来让它们振作起来。于是你想知道有多少个数字是麻木的，这决定了你的工作量。

这道题并非是无聊的。在每一天里，有且仅有一个数字会通过努力练习来增加自己。一旦数字发生变化，它在进一步增值之前不会再发生变化。因此，每天你都需要面临不同的情况。

输入格式

输入的第一行包含一个整数 $T (1 \leq T \leq 10^4)$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n (3 \leq n \leq 2 \times 10^5)$ 和 $q (1 \leq q \leq 2 \times 10^5)$，表示团体里数字的数量以及更新值的次数。

第二行包含 n 个整数 $a_1, a_2, ..., a_n (1 \leq a_i \leq 10^9)$，表示每个数字的值。

接下来 q 行，每行包含两个整数 $p (1 \leq p \leq n)$ 和 $u (1 \leq u \leq 10^9)$，表示被增长的数字标号以及增加的值。

保证所有测试数据中 n 的总和以及 q 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出 q 个整数，表示每次更新后麻木数字的数量。

2
5 3
1 2 3 4 5
2 1
3 2
2 1
4 2
4 5 2 3
4 1
4 3

3
3
3
1
2

解释 #1

• 第一次更新后，数字为 1,3,3,4,5，其中 1,3,3 感到麻木。
• 第二次更新后，数字为 1,3,4,5,5，其中 1,3,4 感到麻木。
• 第三次更新后，数字为 1,4,5,4,5，其中 1,4,4 感到麻木。