Problem:
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?

Incorrect submission (verdict: Wrong Answer):





code_segtree = r
code_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "atcoder",
    sources=["atcoder_library_wrapper.cpp"],
    extra_compile_args=["-O3", "-march=native", "-std=c++14"]
)
setup(
    name="atcoder-library",
    version="0.0.1",
    description="wrapper for atcoder library",
    ext_modules=[module]
)
"""

import os
import sys
if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("atcoder_library_wrapper.cpp", "w") as f:
        f.write(code_segtree)
    with open("setup.py", "w") as f:
        f.write(code_setup)
    os.system(f"{sys.executable} setup.py build_ext --inplace")

from atcoder import SegTree
from operator import itemgetter

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)]


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

op = lambda a, b: a if a > b else b
e = 0
seg = SegTree(op, e, N)
f = lambda x: x == 0
uf = UnionFind(N)
for _, _, y in IXY:
    l = seg.min_left(y, f) - 1
    if l >= 0:
        uf.unite(l, y)
    seg.set(y, 1)
    
#print()
seg = SegTree(op, e, N)
for _, _, y in IXY[::-1]:
    r = seg.max_right(y, f)
    if r < N:
        uf.unite(r, y)
    seg.set(y, 1)
    

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

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


Fixed, accepted submission:
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)))