Problem:
Score : 300 points Problem Statement There are N cities on a 2D plane. The coordinate of the i -th city is (x_i, y_i) . Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N) . For each k = 1,2,\dots,N , find the answer to the following question: Rng is in City k .
Rng can perform the following move arbitrarily many times: move to another city that has a smaller x -coordinate and a smaller y -coordinate, or a larger x -coordinate and a larger y -coordinate, than the city he is currently in. How many cities (including City k ) are reachable from City k ? Constraints 1 \leq N \leq 200,000 (x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N) . (y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N) . All values in input are integers. Input Input is given from Standard Input in the following format: N  x_1  y_1  x_2  y_2  :  x_N  y_N  Output Print N lines. In i -th line print the answer to the question when k = i . Sample Input 1 4
1 4
2 3
3 1
4 2 Sample Output 1 1
1
2
2 Rng can reach City 4 from City 3 , or conversely City 3 from City 4 . Sample Input 2 7
6 4
4 3
3 5
7 1
2 7
5 2
1 6 Sample Output 2 3
3
1
1
2
3
2

Solution (Python):
def main():
    examA()

def examA():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            
            return self.find(x) == self.find(y)

        def size(self, x):
            
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            
            return self.parent[x] < 0

        def roots(self):
            
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            
            return len(self.roots())

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}
    N = I()
    XY = [LI()+[i] for i in range(N)]
    XY.sort()
    
    que = []
    ans = [0]*N
    uf = UnionFind(N)
    for _,y,i in XY:
        if not que:
            heappush(que,[y,i])
        else:
            miny, mini = heappop(que)
            if miny<y:
                uf.unite(i, mini)
                while (que):
                    ny, ni = heappop(que)
                    if ny < y:
                        uf.unite(i, ni)
                        
                    else:
                        heappush(que, [ny, ni])
                        break
            else:
                heappush(que, [y, i])
            heappush(que, [miny, mini])

    for i in range(N):
        ans[i] = uf.size(i)
    for v in ans:
        print(v)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)


n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy=[(i,x,y)for i,(x,y) in enumerate(xy)]
xy.sort(key=lambda x:x[1])
g=[set() for _ in range(n)]
bit=BIT(n)
work=[-1]*(n+1)
for i,x,y in xy:
  k=bit.sum(y)
  l,r=1,y+1
  c=y+1
  for j in range(k,0,-1):
    l,r=1,c
    while r-l>1:
      c=(r+l)//2
      if bit.sum(c)>=j:
        l,r=l,c
      else:
        l,r=c,r
    c=l if bit.sum(l)==j else r
    idx=work[c]
    g[idx].add(i)
    g[i].add(idx)
    if j>1:bit.add(c,-1)
  if k==0:bit.add(y,1)
  if k==0:work[y]=i

ans=[0]*n
mi=set(range(n))
while mi:
  s=mi.pop()
  grp={s}
  todo=[s]
  cnt=1
  while todo:
    v=todo.pop()
    for nv in g[v]:
      if nv not in grp:
        todo.append(nv)
        grp.add(nv)
        mi.discard(nv)
        cnt+=1
  for id in grp:
    ans[id]=cnt
print(*ans,sep='\n')

Solution (Python):

class UnionFind:
    
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    
    def size(self, x):
        return -self.parents[self.find(x)]

from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())

    l = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        l[x-1] = (y-1, i)

    uf = UnionFind(n)
    roots = []

    for y, i in l:
        if len(roots) == 0 or roots[-1][0] > y:
            roots.append((y, i))
        else:
            new_y = roots[-1][0]
            while len(roots) > 0 and roots[-1][0] < y:
                old_y, old_i = roots.pop()
                uf.union(i, old_i)
            roots.append((new_y, i))

    
    for i in range(n):
        print(uf.size(i))

main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class UnionFind:
    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def find(self, x):
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

N = getN()
Q = [getList() for i in range(N)]
que = deepcopy(Q)
que.sort(key = lambda i:i[1], reverse = True)
que.sort()




"""
O(n**2)
U = UnionFind(N)
for i in range(N):
    for j in range(i + 1, N):
        if que[i][1] < que[j][1]:
            U.union(i, j)
for i in range(N):
    print(U.count(i))
"""






















U = UnionFind(N + 1)
group = []

for x, y in que:
    
    if not group:
        group.append(y)
        continue
    
    if y < group[-1]:
        group.append(y)
        continue
    opt = float('inf')
    
    while group:
        
        if y > group[-1]:
            l = group.pop()
            U.union(l, y)
            opt = min(opt, l) 
        else:
            break
    
    group.append(opt)

for i in range(N):
    print(U.count(Q[i][1]))

Solution (Python):

from typing import Iterable
import sys
def main(N, XY):
    uf = UnionFindTree(N)
    miny = []
    for x, y in sorted(XY, key=lambda x: x[0]):
        if not miny:
            miny.append(y)
            continue
        if y < miny[-1]:
            miny.append(y)
            continue
        t = 10**10
        while miny:
            if y > miny[-1]:
                py = miny.pop()
                uf.union(py, y)
                t = min(t, py)
            else:
                break
        miny.append(t)
    for x, y in XY:
        print(uf.size(y))

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    XY = [tuple(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, XY)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        


def main():
    n = int(input())
    town = [list(map(int, input().split())) + [i] for i in range(n)]

    town.sort()
    union = UnionFind(n)
    already = deque([])

    for x, y, i in town:
        if not already:
            already.append((y, i))
            continue
        key = already.pop()
        if key[0] > y:
            already.append(key)
            already.append((y, i))
            continue
        sub = key
        while already:
            union.union(sub[1], i)
            sub = already.pop()
            if sub[0] > y:
                break
        if not already and sub[0] < y:
            union.union(sub[1], i)
        else:
            already.append(sub)
        already.append(key)
    
    ans = [0]*n
    for i in range(n):
        ans[i] = union.size(i)
    
    print(*ans, sep="\n")





    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]


n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
xy2.sort()
u = Unionfind(n)

l = []
for x,y,ind in xy2:
    M = y
    le = ind
    while l and xy[l[-1]][1] < y:
        v = l.pop()
        if M > xy[v][1]:
            M = xy[v][1]
            le = v
        u.union(ind,v)
    l.append(le)
for i in range(n):
    print(u.size(i))

Solution (Python):
import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    l = []
    for x,y,ind in xy2:
        M = y
        le = ind
        while l and xy[l[-1]][1] < y:
            v = l.pop()
            if M > xy[v][1]:
                M = xy[v][1]
                le = v
            u.union(ind,v)
        l.append(le)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    self.min_y = [N]*n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.min_y[x] = min(self.min_y[x],self.min_y[y])
    self.parents[y] = x

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys,os,io
input = sys.stdin.readline

N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
uf = UnionFind(N)
uf.min_y = [y for x,y,i in A]
ans = [1]*N
A.sort()
Y = [(i,y) for x,y,i in A]
from heapq import *
heap = []
for u,y in Y:
  atode = []
  for _ in range(len(heap)):
    y1,v = heappop(heap)
    if y<y1:
      heappush(heap,(y1,v))
      break
    uf.union(u,v)
    if uf.parents[v]<0:
      atode.append((uf.min_y[v],v))
  if uf.parents[u]<0:
    heappush(heap,(uf.min_y[u],u))
  for y1,v in atode:
    heappush(heap,(y1,v))
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Solution (Python):
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *XY = map(int, open(0).read().split())
YtoI = {y : i for i, y in enumerate(XY[1::2])}

uf = UnionFind(N)
Q = []
for x, y in sorted(zip(*[iter(XY)] * 2)):
    heappush(Q, y)
    mi = Q[0]
    while Q and Q[0] <= y:
        uf.union(YtoI[y], YtoI[heappop(Q)])
    heappush(Q, mi)

for i in range(N):
    print(uf.size(i))

Solution (Python):
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *XY = map(int, open(0).read().split())
XY = list(zip(*[iter(XY)] * 2))

YtoI = {y : i for i, (x, y) in enumerate(XY)}

XY.sort()

uf = UnionFind(N)
Q = []
for x, y in XY:
    T = []
    while Q and Q[0] < y:
        yy = heappop(Q)
        uf.union(YtoI[y], YtoI[yy])
        T.append(yy)

    if T:
        heappush(Q, T[0])
    else:
        heappush(Q, y)


for i in range(N):
    print(uf.size(i))

Solution (Python):
n = int(input())
xy = []
idx = [None]*n
ys = [None]*n
ans = [None]*n
accumx = [None]*n
accumn = [None]*n
for i in range(n):
    x, y = map(int, input().split())
    idx[x-1] = i
    ys[x-1] = y-1
accumx[-1] = ys[-1]
for i in range(n-2, -1, -1):
    accumx[i] = max(accumx[i+1], ys[i])
accumn[0] = ys[0]
for i in range(1, n):
    accumn[i] = min(accumn[i-1], ys[i])

def bisect(x):
    ok = 0
    ng = n
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if accumx[mid]>x:
            ok = mid
        else:
            ng = mid
    return ok

nowx = 0
while nowx<n:
    nxtx = nowx
    tmp = bisect(ys[nowx])
    while tmp>nxtx:
        nxtx = tmp
        tmp = bisect(accumn[nxtx])
    if nxtx<nowx:
        nxtx = nowx
    for i in range(nowx, nxtx+1):
        ans[idx[i]] = nxtx-nowx+1
    nowx = nxtx + 1
print(*ans, sep='\n')

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
idx_dic = {}
XY = []
for i in range(N):
    x, y = mapint()
    x, y = x-1, y-1
    idx_dic[i] = y
    XY.append((x, y))
XY.sort()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
from heapq import heappush, heappop
Q = []
for i in range(N):
    x, y = XY[i]
    mini = None
    while Q:
        v = heappop(Q)
        if v>y:
            heappush(Q, v)
            break
        uf.union(v, y)
        if mini is None:
            mini = v
    if mini is None:
        heappush(Q, y)
    else:
        heappush(Q, mini)
for i in range(N):
    print(uf.size(idx_dic[i]))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI()+[i] for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1


    n = I()
    p = LIR(n)
    p.sort()
    par = list(range(n))
    rank = [0]*n
    q = []
    q2 = []
    for x,y,i in p:
        f = 0
        while q:
            yy,j = heappop(q)
            if y < yy:
                heappush(q,(yy,j))
                break
            f = 1
            unite(i,j)
            q2.append((yy,j))
        while q2:
            yy,j = q2.pop()
            heappush(q,(yy,j))
        if not f:
            heappush(q,(y,i))
    s = [0]*(n+1)
    for _,_,i in p:
        s[root(i)] += 1
    ans = [None]*n
    for _,_,i in p:
        ans[i] = s[root(i)]
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
class Unionfind():  
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  
        return -self.parents[self.find(x)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1


uf = Unionfind(n)
cnt, yflag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1]):
    yflag[y] = 1
    cnt += yflag[n - x - 1] + (y > n - x - 1)
    if cnt < x + 1:
        uf.union(x, x + 1)

for x, y in xy:
    print(uf.size(x - 1))

Solution (Python):
class Unionfind():  
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  
        return -self.parents[self.find(x)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1


uf = Unionfind(n)
tmp, yfrag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1]):
    yfrag[y] = 1
    tmp += yfrag[n - x - 1] + (y > n - x - 1)
    if tmp < x + 1:
        uf.union(x, x + 1)

for x, y in xy:
    print(uf.size(x - 1))

Solution (Python):
class Unionfind():  
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  
        return -self.parents[self.find(x)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1


uf = Unionfind(n)
tmp, yfrag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1], 1):
    yfrag[y] = 1
    tmp += yfrag[n - x] + (y > n - x)
    if tmp < x:
        uf.union(x, x - 1)

for x, y in xy:
    print(uf.size(x - 1))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]




import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
xyi = []

for i in range(n):
    x,y = map(int,readline().split())
    xyi.append((x,y,i))

UF = UnionFind(n)
xyi.sort(key = lambda p:p[0])


q = []
for x,y,i in xyi:
    
    if q and q[-1][0] < y: Y,I = q[-1]
    else: Y,I = y,i
    while q and q[-1][0] < y:
        yy,ii = q.pop()
        UF.merge(i,ii)
    q.append((Y,I))
    

for i in range(n):
    print(UF.getsize(i))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY[1:]:
    if B[-1] < y:
        bl = B.pop()
        uf.unite(bl, y)
        while B and B[-1] < y:
            uf.unite(bl, B.pop())
        B.append(bl)
    else:
        B.append(y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))