Совсем недавно Вадим кинул N точек на плоскость с декартовыми координатами. Все точки разлетелись повсюду. Поэтому Вадим решил навести порядок.

Вначале он взял самую верхнюю точку (точку с наибольшей ординатой) и назвал её делегатом всех точек. После чего он построил выпуклую оболочку на всех N точках. Затем он выбрал все точки левее делегата (точки с меньшей абсциссой) и выделил их в отдельное множество. То же самое он сделал со всеми точками правее делегата (точки с большей абсциссой). С этими множествами точек и со всеми последующими Вадим проделал аналогичные операции. Если какое-либо множество оказывалось пустым, то Вадим пропускал его.

В итоге каждая точка побывала делегатом какого-то множества точек, на каждом из таких множеств Вадим построил выпуклую оболочку. В силу свойств выпуклой оболочки каждая из них является либо точкой, либо отрезком, либо выпуклым многоугольником. Назовём размером выпуклой оболочки для точки 1, для отрезка 2, а для выпуклого многоугольника — количество вершин этого многоугольника.

Найдите для каждой данной точки размер выпуклой оболочки множества, делегатом которого она является.

В первой строке дано целое число N — количество точек, кинутых Вадимом (1 ≤ N ≤ 10⁵).

В следующих N строках даны два целых числа x_i и y_i — абсцисса и ордината i-й точки (|x_i|, |y_i| ≤ 10⁹). Гарантируется, что все абсциссы различные и все ординаты различные.

Выведите N целых чисел l_i — размер выпуклой оболочки множества, делегатом которого является i-я точка.