I. Interval Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ intervals $$$[l_i, r_i]$$$. You want to build a graph with $$$n$$$ vertices, where the $$$i$$$-th vertex corresponds to the $$$i$$$-th interval. If two intervals $$$i, j$$$ intersect, add an undirected, unweighted edge between vertices $$$i$$$ and $$$j$$$.

Let $$$d(i, j)$$$ be the length of the shortest path between the $$$i$$$-th vertex and the $$$j$$$-th vertex. If there is no path from $$$i$$$ to $$$j$$$, $$$d(i, j) = 0$$$.

For $$$i = 1, 2, \dots, n$$$, output $$$\sum_{j=1}^n d(i, j)$$$.

Input

In the first line, $$$n$$$ ($$$1\leq n\leq 2\times 10^5$$$).

In the following $$$n$$$ lines, $$$l_i, r_i$$$ ($$$1\leq l_i \lt r_i\leq 2n$$$). It's guaranteed that the endpoints of intervals are distinct.

Output

$$$n$$$ lines, the answer of $$$i = 1, 2, \dots, n$$$.

Example
Input
5
2 3
6 7
1 9
5 10
4 8
Output
7
5
4
5
5