Pty爬山

时间限制:10s      空间限制:512MB

题目描述

在Pty学校附近,有一座名之为岳之麓的高山。Pty很喜欢和(哔——)一起爬山。
山的平面模型如下:
山由一个顶点集:A1,A2…An给定,保证Ai的x单调递增。我们将Ai和Ai+1之间连上线段,表示山的某一段。如下图所示:
 
Pty想要爬到这座山的最高的顶点,当两个顶点的高度相同时,我们认为x比较大的顶点要高一些。Pty不是盲人,所以他将会在爬山时采取一些策略,使得他能够尽量快的到达最高的顶点。
Pty从初始的顶点出发,往左右看去,他将朝他能够看到的最高的顶点方向走去。当走到每一个顶点时,他都会重新观察,如果这时看到的顶点比之前看到的顶点还要高,那么他将选择此时看到的顶点走去,直到他到达最高点为止。
例如上图中:Pty从A4点出发。他能够看到的最高点是A6,所以他将会向右侧走去。当他到达A5号点时,能够看到A1点比A6点更高,所以他会调转方向,向左侧走去。由于A1是最高的顶点,所以他将一直往左侧走,直到到达A1为止。
Pty想知道从每一个顶点出发,分别需要走过多少段才能到达最高点。例如上图中从A4出发需要走过5段才能到达最高点。


输入格式

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


输出格式

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


样例输入

5
1 5
2 4
3 9
4 0
5 2

样例输出

2
1
0
1
2

提示

100%的数据满足:n<=200000, xi<=10^6, yi<= 10^6
此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!


题目来源

没有写明来源