CVJETICI  Cvjetici
On a faraway planet, strange plants with two stems can be found. Every plant on the planet can be described by three numbers: the xcoordinates of the stems L and R, and the height H at which the stems are connect. The image depicts a plant with L=2, R=5 and H=4.
Every day a new plant grows on the planet. The plant that grows on day 1 is of height 1, and every subsequent plant is one higher than the previous one.
When a stem of a new plant intersects the horizontal segment of another plant, a small flower grows (if one wasn't there already). If segments merely touch in a point, a flower will not grow there. The following images are a visualization of the first example.
Write a program that, given the coordinates of all plants, calculates the number of new flower every day.
Input
The first line contains an integer N (1 ≤ N ≤ 100 000), the number of days.
Each of the following N lines contains two integers L and R (1 ≤ L < R ≤ 100 000), the coordinates of the stems of a plant.
Output
Output N lines, the number of new flowers after each plant grows.
Example
Input 4 1 4 3 7 1 6 2 6 Output 0 1 1 2 Input 5 1 3 3 5 3 9 2 4 3 8 Output 0 0 0 3 2
hide comments
ivanmilinovic:
20190329 20:30:40
Very easy problem ac in 1 go


gabrijel:
20190327 23:46:43
I had the same problem as fabijanb, but then I remembered splay tree and quickly got AC (in 1 go ofc) 

fabijanb:
20190327 21:49:37
any help please, I am really stuck with this problem for 13 days already, starting to give up


linkret:
20190327 16:14:29
this task reminds me of the flower "jaglac", which is edible and quite delicious 

shahwat:
20180810 07:36:41
@imperfectboy, there will be no case where L == R. Read the problem statement carefully. 

kspoj:
20171219 18:00:11
Seg Tree :D :D 

imperfectboy:
20171016 03:46:07
1WA !!! don't forget to consider L=R case !!! 

kejzak:
20151207 16:03:37
all works except source limit.. 

Shubham Goyal:
20151201 05:55:44
1d BIT problem


RajatBajaj:
20150626 08:28:52
my 100th..... :) :) 
Added by:  Race with time 
Date:  20090217 
Time limit:  0.203s0.406s 
Source limit:  2000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO PERL6 
Resource:  COCI 2008/2009  Croatian Regional 