레이팅 미적용You finally managed to produce the ultimate stroopwafel with just the right number of squares on it. After the hard work, you left the stroopwafel unattended for a few seconds to get yourself a hot drink. Full of anticipation for your delicious treat, you came back just to see that your stroopwafel was gone! Even though you were only away for a short time, someone used the opportunity to steal it.
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.
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 the convincingness of each suspect.
4
2 8
1 7
4 5
5 2
0 0 1 2
5
2 4
3 3
2 2
4 2
4 1
0 1 1 2 3