Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P175PROD - ROUND 5D - Sự kiện lịch sử 2

Nhờ sự giúp đỡ của các Coder nên Ryze đã hoàn thành bài tập của cô giáo một cách nhanh chóng. Lần này cô giáo Fiora quyết định cho cậu một bài tập khó hơn, các bạn hãy giúp Ryze giải quyết bài tập này:

Lịch sử thế giới bao gồm đúng N sự kiện. Sự kiện thứ i được bắt đầu từ năm ai và kết thúc vào năm bi (ai < bi). Cô cho rằng sự kiện j chứa đựng sự kiện i nếu aj < ai và bj > bi. Đối với mỗi sự kiện lịch sử hãy đếm số sự kiện lịch sử mà nó chứa. 

Input

Dòng đầu chứa số nguyên N (1 <= N <= 2 x 10^5) là số sự kiện xảy ra trong lịch sử.

N dòng tiếp theo, dòng thứ i + 1 chứa 2 số nguyên ai và bi(-10^9 <= ai < bi <= 10^9) là năm bắt đầu và kết thúc của sự kiện thứ i (ai, bi, aj, bj khác nhau đôi một với mọi i, j (i!=j)).

Output

In trên n dòng, dòng thứ i chứa số nguyên duy nhất là số sự kiện lịch sử mà sự kiện thứ i chứa.

Example

Input:
4
-1 9
4 5
2 7
0 1
Output:
3
0
1
0


Được gửi lên bởi:adm
Ngày:2017-03-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.