eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

CodeCoder против TopForces

CodeCoder против TopForces

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Соревновательное программирование очень популярно в Byteland. Фактически, каждый гражданин Байтландии зарегистрирован на двух сайтах программирования - CodeCoder и TopForces. Каждый сайт поддерживает свою собственную рейтинговую систему. Каждый гражданин имеет уникальный целочисленный рейтинг на каждом сайте, который приблизительно соответствует их навыкам. Чем выше рейтинг, тем лучше навык.

Люди Byteland от природы оптимистичны. Гражданин A думает, что у него есть шанс победить гражданина B в соревновании по программированию, если существует последовательность граждан Байтландии A = P[0], P[1], ..., P[k] = B для некоторого k1 такого, что для каждого i (0i < k), P[i] имеет более высокий рейтинг, чем P[i+1] на одном или обоих сайтах.

Каждый гражданин Байтландии хочет знать, сколько других граждан он может победить в соревновании по программированию.

Входные данные

В первой строке записано целое число n (1n100 000) - количество горожан. Следующие n строк содержат информацию о рейтингах. i - ая строка содержит два целых числа CC[i] и TF[i] - рейтинги i - го гражданина на CodeCoder и TopForces (1CC[i], TF[i]10^6). Все рейтинги на каждом сайте разные.

Выходные данные

Для каждого гражданина i выведите целое число b[i] - сколько других граждан они могут победить в соревновании по программированию. Каждое значение b[i] должно быть выведено в отдельной строке в том порядке, в котором граждане указаны во входных данных.

Пример

Входные данные #1
4
2 3
3 2
1 1
4 5
Выходные данные #1
2
2
0
3
Источник 2016 ACM NEERC, Северный регион, Октябрь 22, Задача C