题目描述

在 Pty 学校附近，有一座名之为岳之麓的高山。Pty 很喜欢和（哔——）一起爬山。

山的平面模型如下：

山由一个顶点集： $a_1,a_2…a_n$ 给定，保证 $a_i$ 的 $x$ 单调递增。我们将 $a_i$ 和 $a_{i+1}$ 之间连上线段，表示山的某一段。如下图所示：

Pty 想要爬到这座山的最高的顶点，当两个顶点的高度相同时，我们认为 $x$ 比较大的顶点要高一些。Pty 不是盲人，所以他将会在爬山时采取一些策略，使得他能够尽量快的到达最高的顶点。

Pty 从初始的顶点出发，往左右看去，他将朝他能够看到的最高的顶点方向走去。当走到每一个顶点时，他都会重新观察，如果这时看到的顶点比之前看到的顶点还要高，那么他将选择此时看到的顶点走去，直到他到达最高点为止。

例如上图中：Pty 从 $a_4$ 点出发。他能够看到的最高点是 $a_6$，所以他将会向右侧走去。当他到达 $a_5$ 号点时，能够看到 $a_1$ 点比 $a_6$ 点更高，所以他会调转方向，向左侧走去。由于 $a_1$ 是最高的顶点，所以他将一直往左侧走，直到到达 $a_1$ 为止。

Pty 想知道从每一个顶点出发，分别需要走过多少段才能到达最高点。例如上图中从 $a_4$ 出发需要走过 $5$ 段才能到达最高点。

输入格式

第一行输入 $n$，表示 $n$ 个顶点。
接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个顶点的坐标。
输入保证 $x_i$ 单调递增。

输出格式

输出共 $n$ 行：第 $i$ 行表示从第 $i$ 个顶点出发走到最高点需要经过多少步。

5
1 5
2 4
3 9
4 0
5 2

2
1
0
1
2

样例解释

数据规模与约定

对于 $100\%$ 的数据满足，$n \le 2 \times 10^5$，$x_i \le 10^6$，$y_i \le 10^6$。

此题存在版权，故原 BZOJ 不再支持提交，保留在此只供大家参考题面！ 望见谅！