The Eldest

Time limit3sMemory limit1024 MB

Summary

Each person has a distinct birth year and a death year; count how many years each person was the oldest living resident at the New Year's speech.

Level: Medium7 of 10
Topics: Sorting, Intervals, Simulation, Implementation
Solved: No attempts yet

Problem

A long time ago there was a small village named Stackköping. The residents of Stackköping had several special traditions. One tradition was that at the end of every year, the oldest living resident had to give a New Year's speech. Another tradition was that at most one new person was allowed to be born each year, and according to some experts this was what eventually led to the downfall of Stackköping.

At an archaeological excavation, a document was found showing the years in which all $n$ people who ever lived in Stackköping were born and died. You have come into possession of this document and want to calculate how many New Year's speeches each person gave.

The New Year's speech is always the very last thing that happens each year, so no one is born or dies after the speech that occurs in the same year. If no one is alive at the New Year, then of course no speech is held. Otherwise a speech is always held, even if only one person is alive.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^5$ ): the number of people. The following $n$ lines contain two integers $f_i$ and $d_i$ ( $0 \le f_i < d_i \le 10^9$ ): the years in which person number $i$ was born and died. All the numbers $f_i$ are distinct.

Output

Print $n$ lines with one integer on each, where the $i$ th number is how many New Year's speeches the $i$ th person gave.

Examples3

Example 1
Input
```
4
0 3
4 5
2 5
7 8
```
Expected output
```
3
0
2
1
```

Example 2

Input

7
1763 1844
1799 1859
1826 1872
1829 1907
1858 1950
1882 1973
1946 1000000000

Expected output

Example 3
Input
```
4
1 5
4 8
5 9
2 6
```
Expected output
```
4
2
1
1
```