問題文

Indeed 社には $N$ 人の社員がいます。社員 $i (1 ≦ i ≦ N)$ は時刻 $S_i$ に出社し、時刻 $T_i$ に退社します。各社員は、自分がオフィスにいる間に出社してきた社員に対して "How are you?" と聞きます。すなわち、$S_i < S_j < T_i$ を満たすとき、社員 $i$ は社員 $j$ に対して "How are you?" と聞きます。

あなたは、それぞれの社員が何人に対して "How are you?" と聞くかを計算することにしました。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $T_1$ $S_2$ $T_2$ : $S_N$ $T_N$

• $1$ 行目には、社員の人数を表す整数 $N (1 ≦ N ≦ 10^5)$ が与えられる。
• $2$ 行目からの $N$ 行には、社員の出社時刻と退社時刻の情報が与えられる。このうち $i$ 行目には、$2$ つの整数 $S_i, T_i (1 ≦ S_i < T_i ≦ N\*2)$ が空白区切りで与えられる。これは、社員 $i$ が時刻 $S_i$ に出社し、時刻 $T_i$ に退社することを表す。ただし、$S_i = S_j$ または $S_i = T_j$ を満たすような $i,j (1 ≦ i < j ≦ N)$ は存在しないことが保証される。(16:18削除)
• 与えられる出社時刻と退社時刻は全て相異なる。つまり、$S_1,…,S_N,T_1,…,T_N$ は全て異なる。(16:18追加)

部分点

この問題には部分点が設定されている。

• $N ≦ 2000$ を満たすデータセット $1$ に正解した場合は、$30$ 点が与えられる。
• 全てのテストケースに正解した場合は、上記とは別に $70$ 点が与えられる。

出力

出力は $N$ 行からなる。このうち $i$ 行目には、社員 $i$ が "How are you?" と聞く社員の人数を表す $1$ つの整数を出力せよ。出力の末尾にも改行を入れること。

入力例1

4
1 6
2 4
3 7
5 8

出力例1

3
1
1
0

この入力例では、

• 社員 $1$ は、社員 $2$ と 社員 $3$ と社員 $4$ に対して "How are you?" と聞きます。
• 社員 $2$ は、社員 $3$ に対して "How are you?" と聞きます。
• 社員 $3$ は、社員 $4$ に対して "How are you?" と聞きます。
• 社員 $4$ は、誰にも "How are you?" と聞きません。

入力例2

7
5 12
10 11
1 2
6 13
4 7
3 8
9 14

出力例2

3
0
0
2
2
3
1