题目描述

给出一些山顶的坐标($x_i,y_i$)，我们认为山是这些山顶构成的一段折线$l$。 每到一个山顶以后，你会左右张望找到能看到的最高的山顶（一个山顶$P$能被他们看到当且仅当连接你与$P$的线段与$l$只在你和$P$上相交），并向到目前为止你看到过的最高的山顶那个方向继续前进（爬到左边相邻的一个山顶或右边相邻的一个山顶）。 爬到最高的山顶后你会停下来。 对于每个山顶，求出若你选择此处作为爬山起点的话，你会爬过几个山顶（经过多次算多次）。 注意：$y$坐标相同情况下选取$x$坐标最大的为最高山顶。

输入

第一行一个整数$n$表示山顶的数量。 接下来的$n$行，每行两个整数$x_i,y_i$。保证$x_i$单调递增。

输出

$n$行，每行一个整数表示从($x_i,y_i$)出发的答案。

输入样例

4
0 10
1 5
2 0
3 6

输出样例

0
1
4
3

提示

【数据规模】 对于30%的数据，$n≤100$。 对于60%的数据，$n≤5×10^4$。 对于100%的数据，$1≤n≤5×10^5，0≤x_i,y_i≤10^6$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。