output_description: Print N lines. In i-th line print the answer to the question when k = i.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1
      x_2 y_2
      :
      x_N y_N
attempt: import sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  
  class UnionFindTree:
      def __init__(self, n):
          self.n = n
          self.parent = list(range(n))
          self.size = [1] * n
  
      def root(self, i):
          inter = set()
          while self.parent[i] != i:
              inter.add(i)
              i = self.parent[i]
          r = i
          for i in inter:
              self.parent[i] = r
          return r
  
      def connect(self, i, j):
          ri = self.root(i)
          rj = self.root(j)
          if ri == rj:
              return
          if self.size[ri] < self.size[rj]:
              self.parent[ri] = rj
              self.size[rj] += self.size[ri]
          else:
              self.parent[rj] = ri
              self.size[ri] += self.size[rj]
  
  
  ### BIT binary
  def init(bit, values):
      for i, v in enumerate(values):
          add(bit, i + 1, v)
  
  
  # a1 ~ aiまでの和 O(logn)
  def query(bit, i):
      res = 0
      while i > 0:
          res += bit[i]
          i -= i & (-i)
      return res
  
  
  # ai += x(logN)
  def add(bit, i, x):
      if i == 0:
          raise RuntimeError
      while i <= len(bit) - 1:
          bit[i] += x
          i += i & (-i)
      return
  
  
  def index(bit, v):
      """a1,...,aiの和がv以上になる最小のindexを求める
      存在しないとき配列サイズを返す
      """
      i = 0
      n = len(bit) - 1
      k = 1 << ((n - 1).bit_length())
      while k > 0:
          if i + k < n + 1 and bit[i + k] < v:
              v -= bit[i + k]
              i += k
          k //= 2
      if v == 1:
          return i + 1
      else:
          return n + 1
  
  
  n = int(input())
  xy = []
  dx = {}
  dy = {}
  for i in range(n):
      x, y = map(lambda x: int(x) - 1, input().split())
      xy.append((i, x, y))
      dx[x] = i
      dy[y] = i
  
  uf = UnionFindTree(n)
  xy.sort(key=lambda item: item[1])
  
  bit = [0] * (n + 1)
  for i, x, y in xy:
      num = query(bit, y + 1)
      if num > 0:
          ii = dy[index(bit, num) - 1]
          uf.connect(i, ii)
      add(bit, y + 1, 1)
  bit = [0] * (n + 1)
  c = 0
  for i, x, y in reversed(xy):
      num = query(bit, y + 1)
      if c - num > 0:
          ii = dy[index(bit, num + 1) - 1]
          uf.connect(i, ii)
      add(bit, y + 1, 1)
      c += 1
  
  xy.sort(key=lambda item: item[2])
  bit = [0] * (n + 1)
  for i, x, y in xy:
      num = query(bit, x + 1)
      if num > 0:
          ii = dx[index(bit, num) - 1]
          uf.connect(i, ii)
      add(bit, x + 1, 1)
  bit = [0] * (n + 1)
  c = 0
  for i, x, y in reversed(xy):
      num = query(bit, x + 1)
      if c - num > 0:
          ii = dx[index(bit, num + 1) - 1]
          uf.connect(i, ii)
      add(bit, x + 1, 1)
      c += 1
  
  ans = [None] * n
  for i in range(n):
      ans[i] = uf.size[uf.parent[i]]
  write("\n".join(map(str, ans)))
  
problem_description: 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?
samples: [{"input": "4\n    1 4\n    2 3\n    3 1\n    4 2", "output": "1\n    1\n    2\n    2\n    \n\nRng can reach City 4 from City 3, or conversely City 3 from City 4.\n\n* * *"}, {"input": "7\n    6 4\n    4 3\n    3 5\n    7 1\n    2 7\n    5 2\n    1 6", "output": "3\n    3\n    1\n    1\n    2\n    3\n    2"}]