Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only 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.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Nested Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 2·10^{5}) — the number of segments on a line.

Each of the next *n* lines contains two integers *l*_{i} and *r*_{i} ( - 10^{9} ≤ *l*_{i} < *r*_{i} ≤ 10^{9}) — 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.

Output

Print *n* lines. The *j*-th of them should contain the only integer *a*_{j} — the number of segments contained in the *j*-th segment.

Examples

Input

4

1 8

2 3

4 7

5 6

Output

3

0

1

0

Input

3

3 4

1 5

2 6

Output

0

1

1

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2022 13:35:17 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|