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):
n=int(input())
n+=1
p=[0]*n
a=[0]*n
b=[0]*n
for i in range(1, n):
    p[i],a[p[i]]=map(int,input().split())
m=n+1
c=0
for i in range(1,n):
    m=min(m,a[i])
    if n-i==m:
        d=i-c
        while c<i:
            c+=1
            b[c]=d
for i in range(1,n):
    print(b[p[i]])

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())
L = []
for i in range(N):
    L.append(list(map(int,input().split())) + [i])
L.sort()

SUM1 = 0
SUM2 = 0
UFT = UnionFind(N)
for i in range(N-1):
    SUM1 += N - i
    SUM2 += L[i][1]
    if SUM1 != SUM2:
        UFT.union(i, i+1)
ans = [0] * N
for i in range(N):
    ans[L[i][2]] = UFT.size(i)
for i in range(N):
    print(ans[i])

Solution (Python):
from bisect import bisect_left
from collections import Counter
import sys

def main():
    input = sys.stdin.readline
    N = int(input().rstrip())
    
    parent = list(range(N))
    rank = [1] * N
    def get_root(node):
      if parent[node] == node:
        return node
      root = get_root(parent[node])
      parent[node] = root
      return root
    
    def union(a, b):
      root_a = get_root(a)
      root_b = get_root(b)
      if root_a == root_b:
        return
      rank_a = rank[root_a]
      rank_b = rank[root_b]
      if rank_a < rank_b:
        parent[root_a] = root_b
      else:
        parent[root_b] = root_a
        if rank_a == rank_b:
          rank[root_a] += 1

    XYs = []
    XYs1 = []
    XYs2 = []
    for i in range(N):
        x, y = map(int, input().rstrip().split())
        XYs.append([x, y, i])
        XYs2.append([N-x, N-y, i])
    XYs1 = sorted(XYs)
    XYs2.sort()
    
    buf = []
    L = 0
    for x, y, k in XYs1:
        idx = bisect_left(buf, [-y, k])
        if idx == L:
            buf.append([-y, k])
        else:
            ny, nk = buf[-1]
            while L > idx:
                ty, tk = buf.pop()
                union(k, tk)
                L -= 1
            buf.append([ny, nk])
        L += 1
    
    buf = []
    L = 0
    for x, y, k in XYs2:
        idx = bisect_left(buf, [-y, k])
        if idx == L:
            buf.append([-y, k])
        else:
            ny, nk = buf[-1]
            while L > idx:
                ty, tk = buf.pop()
                union(k, tk)
                L -= 1
            buf.append([ny, nk])
        L += 1

    ct = Counter()
    for i in range(N):
        ct[get_root(i)] += 1
    
    for p in parent:
        print(ct[p])

main()

Solution (Python):
import sys, math
import io, os

from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal


mod = 998244353
INF=float('inf')



n=int(input())
BIT = [0]*(n+1)
d1=dd(int)
d2=dd(int)
d=dd(int)
for i in range(n):
    x,y=mdata()
    d1[x]=y
    d2[y]=x
    d[x]=i
l2=list(range(1,n+1))
l1=l2[::-1]
ans=[0]*n
while l1:
    set1=set()
    s=0
    mx=l1[-1]
    my=d1[l1[-1]]
    set1.add(l1.pop())
    while len(set1)!=s:
        s=len(set1)
        while l2 and l2[-1]>=my:
            set1.add(d2[l2[-1]])
            mx=max(mx,d2[l2.pop()])
        while l1 and l1[-1]<=mx:
            set1.add(l1[-1])
            my=min(my,d1[l1.pop()])
    l=len(set1)
    for i in set1:
        ans[d[i]]=l
outl(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
XYI.sort()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

import heapq
hq = []
uf = UnionFind(N)
for x,y,i in XYI:
    miny = mini = None
    while hq and hq[0][0] < y:
        ty,ti = heapq.heappop(hq)
        if miny is None:
            miny, mini = ty, ti
        uf.unite(i,ti)
    if miny is None:
        heapq.heappush(hq, (y,i))
    else:
        heapq.heappush(hq, (miny,mini))

ans = []
for i in range(N):
    ans.append(uf.size(i))
print(*ans, sep='\n')

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x>=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2>=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Solution (Python):
import sys
n=int(input())
def unite(x,y):
	if same(x,y)==False:
		rx=root(x);ry=root(y)
		if rank[rx]>rank[ry]:
			parent[ry]=rx
			size[rx]+=size[ry]
		else:
			parent[rx]=ry
			size[ry]+=size[rx]
			if rank[rx]==rank[ry]:
				rank[ry]+=1
def root(x):
	if x!=parent[x]:
		return root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
parent=list(range(n))
rank=[0]*n
size=[1]*n

xy=[]
for i in range(n):
	x,y=map(int,input().split())
	xy.append((x,y,i))
xy.sort()
LIS=[[xy[0][1],xy[0][2]]]
from heapq import heappop,heappush
for x,y,i in xy[1:]:
	flag=False
	now=LIS[0]
	while LIS and LIS[0][0]<y:
		flag=True
		unite(i,LIS[0][1])
		heappop(LIS)
	if flag:
		heappush(LIS,now)
	else:
		heappush(LIS,[y,i])
for i in range(n):
	print(size[root(i)])

Solution (Python):
n=int(input())
n+=1
p=[0]*n
a=[0]*n
an=[0]*n
for i in range(1, n):
    p[i],a[p[i]]=map(int,input().split())
mi=n+1
cu=0
for i in range(1,n):
    if mi>a[i]:
        mi=a[i]
    if n-i==mi:
        cn=i-cu
        while cu<i:
            cu+=1
            an[cu]=cn
for i in range(1,n):
    print(an[p[i]])

Solution (Python):


import sys
input=sys.stdin.readline
n=int(input())
xy=[0]*(n+1)
xid=[0]*(n+1)
for i in range(n):
    xi,yi=map(int, input().split())
    xy[xi]=yi
    xid[xi]=i


*p,=range(n+1)
r=[0]*(n+1)
def par(x):
    if p[x]==x:
        return x
    res = p[x]=par(p[x])
    return res

def union(x,y):
    px=par(x);py=par(y)
    if px==py:
        return
    if r[px]>r[py]:
        p[py]=px
        r[py]+=1
    elif r[px]<r[py]:
        p[px]=py
        r[px]+=1
    else:
        p[px]=py
        r[py]+=1

stk=[(xy[1],1)]
for x in range(2,n+1):
    y=xy[x]
    if y>stk[-1][0]:
        yy,xx=stk.pop()
        union(x,xx)
        while stk and y>stk[-1][0]:
            union(x,stk[-1][1])
            stk.pop()
        stk.append((yy,xx))
    else:
        stk.append((y,x))
for i in range(1,n+1):par(i)

from collections import Counter
cp=Counter(p)
ans=[0]*n
for i in range(1,n+1):
    ans[xid[i]]=cp[par(i)]
for ai in ans:
    print(ai)

Solution (Python):
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][0]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][1])
        G[xy[i][1]].append(p[1])
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][0], xy[i][1]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Solution (Python):
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [x, y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][1], xy[i][2]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Solution (Python):
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append([x, y, i])
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][1], xy[i][2]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Solution (Python):
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append([x, y, i])
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

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

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()}

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

def main():
    n = int(input())
    xy = [list(map(int, input().split())) + [i] for i in range(n)]
    xy.sort()
    UF = UnionFind(n)
    lst = [[xy[0][1], xy[0][2]]]
    
    for _, y, i in xy[1:]:
        flg = False
        tmp = lst[0]
        while lst and lst[0][0] < y:
            flg = True
            pos = lst[0][1]
            UF.union(i, pos)
            heapq.heappop(lst)
        if flg:
            heapq.heappush(lst, tmp)
        else:
            heapq.heappush(lst, [y, i])
    for i in range(n):
        print(UF.size(i))
    
main()

Solution (Python):
import heapq

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()}

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

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
xy.sort()
UF = UnionFind(n)
lst = [[xy[0][1], xy[0][2]]]

for _, y, i in xy[1:]:
    flg = False
    tmp = lst[0]
    while lst and lst[0][0] < y:
        flg = True
        pos = lst[0][1]
        UF.union(i, pos)
        heapq.heappop(lst)
    if flg:
        heapq.heappush(lst, tmp)
    else:
        heapq.heappush(lst, [y, i])
for i in range(n):
    print(UF.size(i))

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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


N = int(input())

uf = UnionFind(N)

xy = []
min_y = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append((x, y, i))
    min_y.append(y)

xy.sort()

min_y = N+1

for i in range(N-1):
    x, y, a = xy[i]
    x1, y1, b = xy[i+1]
    min_y = min(min_y, y)
    if min_y != N - i:
        uf.union(a, b)

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

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    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 unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
s_xy = sorted(xy)
UF = UnionFind(n)
cur = 0
f = [False for i in range(n)]
for i, x in enumerate(s_xy[:n - 1], 1):
    f[x[1] - 1] = True
    if f[n - i] == 1:
        cur += 1
    if x[1] - 1 > n - i:
        cur += 1
    if cur < i:
        UF.unite(i, i - 1)
for i in range(n):
    print(UF.size(xy[i][0] - 1))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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):
        """
        yをxの根に繋ぐ
        """
        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 same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    XY_sort = sorted([[xy[0], xy[1], i] for i, xy in enumerate(XY)])

    uf = UnionFind(n)
    stack = []
    for x, y, idx in XY_sort:
        mi = y
        mi_idx = idx
        while stack and XY[stack[-1]][1] < y:
            v = stack.pop()
            if mi > XY[v][1]:
                mi = XY[v][1]
                mi_idx = v
            uf.union(idx, v)
        stack.append(mi_idx)

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


if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
xy = []
idx = [None]*n
ys = [None]*n
ans = [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
accumn[0] = ys[0]
for i in range(1, n):
    accumn[i] = min(accumn[i-1], ys[i])

b = 0
for i in range(n):
    if accumn[i]==n-i-1:
        for j in range(b, i+1):
            ans[idx[j]] = i-b+1
        b = i+1
print(*ans, sep='\n')

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
rem_max = N
cum_min = N+1
lis = []
for x,y in A:
  cum_min = min(cum_min, y)
  lis.append(y)
  if len(lis)==rem_max-cum_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    rem_max = cum_min-1
    lis = []
    cum_min = N+1
print(*ans, sep='\n')

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
rem_max = N
cum_max = 0
cum_min = N+1
lis = []
for x,y in A:
  cum_max = max(cum_max, y)
  cum_min = min(cum_min, y)
  lis.append(y)
  if cum_max==rem_max and len(lis)==cum_max-cum_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    rem_max = cum_min-1
    lis = []
    cum_max = 0
    cum_min = N+1
print(*ans, sep='\n')

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)

        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])

        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            t = self.ide_ele
            while L < R:
                if L & 1:
                    s = self.segf(s,self.data[L])
                    L += 1
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        
        
        
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1

            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0

    class UnionFind:
        def __init__(self, N: int):
            """
            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: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """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: int, y: int):
            """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=I()
    X=[0]*N
    Y=[0]*N
    
    from collections import defaultdict
    dd = defaultdict(int)
    X2Y = defaultdict(int)
    
    for i in range(N):
        X[i],Y[i]=MI()
        X[i]-=1
        Y[i]-=1
        
        X2Y[X[i]]=Y[i]
        dd[Y[i]]=i
        
    X.sort()
    uf=UnionFind(N)
    
    inf = 10**7
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    
    
    for i in range(N):
        y=X2Y[X[i]]
        k=dd[y]
        yM=seg.query(0,y)
        kM=dd[yM]  
        if yM>=0:
            uf.union(k,kM)
            
        ym=seg2.query(0,y)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)
        
        seg.update(y,y)
        seg2.update(y,y)
        
    
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    for i in range(N-1,-1,-1):
        y=X2Y[X[i]]
        k=dd[y]
        yM=seg.query(y,N)
        kM=dd[yM]  
        if yM>=0:
            uf.union(k,kM)
            
        ym=seg2.query(y,N)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)

        seg.update(y,y)
        seg2.update(y,y)
        
    roots=[0]*N
    for i in range(N):
        y=X2Y[X[i]]
        k=dd[y]
        roots[k]=uf.find(k)
        
    ddr = defaultdict(lambda:-1)
        
    for i in range(N):
        root=roots[i]
        if ddr[root]!=-1:
            print(ddr[root])
        else:
            ans=uf.count(root)
            print(ans)
            ddr[root]=ans
        
        
        
    
    

main()

Solution (Python):
N, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]
XtoY = [0] * (N+1)
for x, y in zip(X,Y):
  XtoY[x] = y

ans = [0] * (N+1)
l = 1
min_y = N + 1
for x in range(1, N+1):
  min_y = min(min_y, XtoY[x])
  if x + min_y == N+1:
    for i in range(l, x+1):
      ans[i] = x - l + 1
    l, min_y = x+1, N+1

for x in X:
  print(ans[x])