Counting Visible Buildings

There are N buildings waiting to be constructed on a construction site, arranged along the x-axis. The i-th building is represented by a vertical line segment from \( (i,0) \) to \( (i, H_i) \) in the 2D plane. At the start (day 0), all buildings have a height of 0.

An observer is located at \( (0,0) \). A building is considered visible if and only if there exists a point on the building (with height \(>0\)) such that the line segment connecting \( (0,0) \) and that point does not intersect any of the segments representing the buildings that lie before it. In this problem, you can prove that the optimal choice is to consider the top of the building. Hence, the i-th building (with \(H_i>0\)) is visible if and only if its slope \[ \frac{H_i}{i} > \max_{1 \le j < i} \frac{H_j}{j}, \] where the maximum is taken over all buildings with index less than \(i\). Note that if \(H_i=0\), the building is not visible.

The construction team works for M days. On day \(k\) (\(1 \le k \le M\)), they update the height of the building at position \(X_k\) to \(Y_k\) (this change can be an increase, decrease or no change). After each day's update, determine how many buildings are visible.

inputFormat

The first line contains two integers \(N\) and \(M\) \( (1 \le N,M \le 10^5)\) representing the number of buildings and the number of days, respectively.

Each of the following \(M\) lines contains two integers \(X_i\) and \(Y_i\) \( (1 \le X_i \le N,\ 0 \le Y_i \le 10^9)\) indicating that on the \(i\)-th day, the height of the building at position \(X_i\) is updated to \(Y_i\).

outputFormat

Output \(M\) lines. The \(i\)-th line should contain a single integer – the number of visible buildings after the \(i\)-th day's update.

sample

5 5
1 5
3 10
3 20
2 8
5 15

1
1
2
2
2