Соревновательное программирование очень популярно в Byteland. Фактически, каждый гражданин Байтландии зарегистрирован на двух сайтах программирования - CodeCoder и TopForces. Каждый сайт поддерживает свою собственную рейтинговую систему. Каждый гражданин имеет уникальный целочисленный рейтинг на каждом сайте, который приблизительно соответствует их навыкам. Чем выше рейтинг, тем лучше навык.
Люди Byteland от природы оптимистичны. Гражданин A думает, что у него есть шанс победить гражданина B в соревновании по программированию, если существует последовательность граждан Байтландии A = P[0]
, P[1]
, ..., P[k]
= B для некоторого k ≥ 1 такого, что для каждого i (0 ≤ i < k), P[i]
имеет более высокий рейтинг, чем P[i+1]
на одном или обоих сайтах.
Каждый гражданин Байтландии хочет знать, сколько других граждан он может победить в соревновании по программированию.
В первой строке записано целое число n (1 ≤ n ≤ 100 000) - количество горожан. Следующие n строк содержат информацию о рейтингах. i - ая строка содержит два целых числа CC[i]
и TF[i]
- рейтинги i - го гражданина на CodeCoder и TopForces (1 ≤ CC[i]
, TF[i]
≤ 10^6
). Все рейтинги на каждом сайте разные.
Для каждого гражданина i выведите целое число b[i]
- сколько других граждан они могут победить в соревновании по программированию. Каждое значение b[i]
должно быть выведено в отдельной строке в том порядке, в котором граждане указаны во входных данных.