题目背景

小周家窗外正对着一大片施工工地，工地上的房子拆了又建、建了又拆。闲来无事，他总爱趴在窗边数一数：自己究竟能看到多少栋房子。

题目描述

把问题简化到二维平面上：小周站在 $(0,0)$ 点，第 $i$ 栋楼房是一条连接 $(i,0)$ 与 $(i,H_i)$ 的线段，$H_i$ 为第 $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

1
1
1
2

提示

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