403027: GYM100971 H Pavel's Party

Pavel is going to have a party, and he wants to invite exactly k people.

Pavel has n friends and he has already decided in what order he is going to call and invite them. When Pavel calls the i-th friend, he tells he will come if from a_i to b_i people come to the party.

Once the required number of people is assembled, Pavel invites them and the party is arranged. Pavel won't call the rest friends.

For every k = 1, ..., n find the number of people whom Pavel will call.

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of Pavel's friends.

Each of the next n lines contains two integers a_i and b_i (1 ≤ a_i ≤ b_i ≤ n) — the lower and the upper bound of the invited people required for the i-th Pavel's friend to come.

The data is listed in the order Pavel will get to know it.

Output n space-separated integers. The k-th number should be equal to the number of friends called by Pavel if he wants to invite exactly k people to the party. If for some k the party cannot be arranged, output  - 1 for this k.

6
3 3
1 2
3 6
3 4
1 4
4 6

2 5 4 6 -1 -1

3
3 3
1 3
3 3

2 -1 3