C - Upgrade Required Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ある OS のバージョンは N 個あり、古い順に 1,2,\dots,N の番号がついています。
PC が N 台あり、初めは i 番目の PC の OS のバージョンは i です。

Q 回の操作を順に行ってください。そのうち i 回目は次の通りです。

  • 現時点での OS のバージョンが X_i かそれ以前の PC 全てを、バージョンを Y_i(>X_i) にアップグレードする。その後、この操作でアップグレードを行った PC の台数を出力する。

i<Q について、 i 回目の操作でのアップグレードが行われた状態で i+1 回目の操作に進むことに注意してください。

制約

  • 入力は全て整数
  • 2 \le N \le 10^6
  • 1 \le Q \le 2 \times 10^5
  • 1 \le X_i < Y_i \le N

入力

入力は以下の形式で標準入力から与えられる。

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

出力

Q 行出力せよ。
そのうち i 行目には、 i 回目の操作でアップグレードを行った PC の台数を出力せよ。

入力例 1

8 5
2 6
3 5
1 7
5 7
7 8

出力例 1

2
1
0
3
7

この入力には 5 回の操作が含まれます。

  • はじめ、 8 台の PC のバージョンは 1,2,3,4,5,6,7,8 です。
  • 1 回目の操作で、バージョンが 2 かそれ以前のバージョンの PC をバージョン 6 にアップグレードします。
    • この操作によって 2 台の PC がアップグレードされ、各 PC のバージョンは 6,6,3,4,5,6,7,8 となります。
  • 2 回目の操作で、バージョンが 3 かそれ以前のバージョンの PC をバージョン 5 にアップグレードします。
    • この操作によって 1 台の PC がアップグレードされ、各 PC のバージョンは 6,6,5,4,5,6,7,8 となります。
  • 3 回目の操作で、バージョンが 1 かそれ以前のバージョンの PC をバージョン 7 にアップグレードします。
    • この操作によって 0 台の PC がアップグレードされ、各 PC のバージョンは 6,6,5,4,5,6,7,8 となります。
  • 4 回目の操作で、バージョンが 5 かそれ以前のバージョンの PC をバージョン 7 にアップグレードします。
    • この操作によって 3 台の PC がアップグレードされ、各 PC のバージョンは 6,6,7,7,7,6,7,8 となります。
  • 5 回目の操作で、バージョンが 7 かそれ以前のバージョンの PC をバージョン 8 にアップグレードします。
    • この操作によって 7 台の PC がアップグレードされ、各 PC のバージョンは 8,8,8,8,8,8,8,8 となります。

Score : 300 points

Problem Statement

There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.

Perform Q operations in order. The i-th operation is as follows:

  • Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.

Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.

Constraints

  • All input values are integers.
  • 2 \le N \le 10^6
  • 1 \le Q \le 2 \times 10^5
  • 1 \le X_i < Y_i \le N

Input

The input is given from Standard Input in the following format:

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

Output

Output Q lines.
The i-th line should contain the number of PCs upgraded in the i-th operation.

Sample Input 1

8 5
2 6
3 5
1 7
5 7
7 8

Sample Output 1

2
1
0
3
7

This input contains five operations.

  • Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
  • In the first operation, PCs with version 2 or earlier are upgraded to version 6.
    • This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
  • In the second operation, PCs with version 3 or earlier are upgraded to version 5.
    • This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
  • In the third operation, PCs with version 1 or earlier are upgraded to version 7.
    • This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
  • In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
    • This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
  • In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
    • This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.