Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
4 1 8 2 3 4 7 5 6
3 0 1 0
3 3 4 1 5 2 6
0 1 1
Codeforces (c) Copyright 2010-2017 Mike Mirzayanov