1012: 买房

拔娜娜很有钱，现在要给娜娜买房。

这个世界的房子都建在二维平面上，总共有 $n(n\le 10^5)$栋房子，每栋房子都是线段，第$i$房子是线段$(i, 0)-(i, h_i)$，$h_i$是第$i$栋房子的高度。

娜娜站在原点向$x$正半轴看，如果从原点到某栋楼楼顶的连线不与其他的楼相交(交在之前的楼顶的话也看不到)，那么娜娜就看得到这栋楼。

一开始，每栋房子高度都是$0$。每天，都会有某一栋房屋的高度都会被修改。

娜娜很任性，看到的高度大于$0$房子都要买，如果高度为$0$，就看不到。求对于接下来$m(m\le 100000)$天，如果拔娜娜在这天给娜娜买房子，他需要买多少栋。

数据第一行表示数据组数$T(T\le 3)$

每组数据的第一行两个整数$n, m$，意义如题目描述。

之后$m$行，每行两个整数$id, height(id \le n, 1 \le height \le 10^9)$，表示$id$号房子的高度改成了$height$，注意$height \ge 1$，也就是说，改完之后的房子高度肯定不是$0$。

输出m个整数，表示对于每一天，拔娜娜需要买房的话会买几栋。

不同组数据之间不需要空行。

1 3 4 2 4 3 6 1 1000000000 1 1

1 1 1 2

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！