Павел собирает друзей на тусовку и хочет, чтобы на ней присутствовало ровно k человек.
Всего у Павла n друзей, и он уже решил, в каком порядке он будет им звонить и приглашать на тусовку. Когда Павел звонит i-му другу, тот сообщает ему, что готов прийти, если всего в тусовке будет участвовать от ai до bi человек.
Как только набирается нужное количество людей, Павел сообщает им об этом, и все организовывается. При этом он не звонит оставшимся друзьям.
Для каждого значения k = 1, ..., n найдите, скольким людям позвонит Павел.
В первой строке записано целое число n (1 ≤ n ≤ 200000) — количество друзей Павла.
В каждой из следующих n строк записано по два целых числа ai и bi (1 ≤ ai ≤ bi ≤ n) — нижняя и верхняя границы количества участников тусовки, при которых i-й друг Павла согласится в ней участвовать.
Данные перечислены в том порядке, в котором Павел будет их узнавать.
Выведите n чисел через пробел. k-е число должно быть равно количеству друзей, которым позвонит Павел, если он хочет, чтобы на тусовке собралось ровно k человек. Если для какого-то k тусовку устроить вообще не получится, выведите для этого k число - 1.
6
3 3
1 2
3 6
3 4
1 4
4 6
2 5 4 6 -1 -1
3
3 3
1 3
3 3
2 -1 3
