Problem D
Justice Served
You looked at the security recordings and saw a total of $n$ suspects that had been in the room where you left your stroopwafel, each entering and leaving the room exactly once. After seeing this, you already had a good idea who took it since your archrival Rob – who has some background in robberies – was among the suspects. But you wanted to give him the benefit of the doubt and decided to interrogate every suspect. Unsurprisingly, every suspect claimed their own innocence. However, some suspects also provided an alibi for other suspects. Specifically, a suspect $A$ provided an alibi for suspect $B$ if and only if $A$ was in the room for the entire duration $B$ was in the room.
You feel like a suspect is more convincing if they have an alibi provided by a suspect who is convincing themselves. Formally, a suspect without an alibi has convincingness $0$. Otherwise, their convincingness is $1$ more than the convincingness of the most convincing suspect who provides them with an alibi. Your task is to compute the convincingness of each suspect.
Input
The input consists of:
-
One line with a single integer $n$ ($1\leq n\leq 2\cdot 10^5$), the number of suspects.
-
$n$ lines, each with two integers $a$ and $t$ ($1\leq a,t\leq 10^9$), the time at which each suspect arrived and the duration they stayed.
It is guaranteed that no two suspects who arrived at the same moment stayed for the same duration.
Output
Output the convincingness of each suspect.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 8 1 7 4 5 5 2 |
0 0 1 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 4 3 3 2 2 4 2 4 1 |
0 1 1 2 3 |
