Description

On a number line there are $n$ points, namely $1, 2, \ldots, n$. Initially, all points are colored black. Then we perform $m$ operations; in the $i$-th operation, the points in $[l_i,r_i]$ are painted white. Output the number of black points remaining after each operation.

Input Format

The first line contains $n$ and $m$. Each of the next $m$ lines contains two integers $l_i$, $r_i$.

Output Format

Output $m$ lines, where each line is the number of black points remaining after the corresponding operation.

10 3
3 3
5 7
2 8

9
6
3

Hint

• For 30% of the testdata, $1\le n\le 2000$, $1\le m\le 2000$.
• For 100% of the testdata, $1\le l_i\le r_i\le n\le 2\times 10^5$, $1\le m\le 2\times 10^5$.

Translated by ChatGPT 5