题目背景

小蔡同学最近搬进了一间视野极好的新宿舍。宿舍窗外是一大片正准备开发的商业区，规划中要修建一排整齐的高楼。可惜施工队显然不是很靠谱，每天都在随机地推倒或加高某一栋楼，仿佛在玩积木。

小蔡同学每天起床后的第一件事，就是端着一杯咖啡站在窗前，观察从他所在位置 ((0,0)) 能看到多少栋楼。他把这称为“楼房可见性指数”。他声称这个指数直接影响他一天的学习效率（虽然大家都不怎么信）。

为了满足小蔡奇怪的爱好，我们给出施工队每天对某栋楼高度的修改，希望你帮他计算每天施工完后，他能看到多少栋楼。

题目描述

整个施工区沿着一条直线分布，共有 (N) 栋计划建造的楼房。我们简化为一个二维平面：第 (i) 栋楼房是连接点 ((i, 0)) 与 ((i, H_i)) 的线段，其中 (H_i) 是该楼的高度。

小蔡同学站在 ((0,0)) 看向右侧的所有楼房。若第 (i) 栋楼房存在某个高度大于 0 的点，使得从 ((0,0)) 到该点的连线不与任意前面（下标更小）的楼房线段相交，则该楼房被认为是 可见的。

施工队将持续施工 (M) 天。最开始所有楼房高度均为 0。第 (i) 天施工队会把横坐标为 ( $X_i$ ) 的楼房高度改为 ( $Y_i$ )（可能变高、变矮或保持不变）。

请你帮助小蔡同学计算每一天施工结束后，他能看到多少栋楼。

第一行两个正整数 $N,M$ 。

接下来 $M$ 行，每行两个正整数 $X_i,Y_i$ 。

$M$ 行，第 $i$ 行一个整数表示第 $i$ 天过后小蔡能看到的楼房有多少栋。

3 4
2 4
3 6
1 1000000000
1 1

对于 $30\%$ 的数据， $1 \le X_i \le N$ ， $1 \le Y_i \le 10^3$ ， $1\le N,M \le 10^3$ 。

对于 $100\%$ 的数据， $1 \le X_i \le N$ ， $1 \le Y_i \le 10^9$ ， $1\le N,M \le 10^5$ 。