بخش ها
Problem
یک خط مستقیم وجود دارد که به رنگ سفید است. n بخش سیاه یکی یکی به آن اضافه می شود.
تعداد بخش‌های سیاه متصل (یعنی تعداد بخش‌های سیاه در اتحاد) را بعد از هر بخش اضافه کنید.
به طور خاص، در نظر بگیرید که اگر یک پاره به نقطه x ختم شود و پاره دیگر در نقطه x شروع شود، آنگاه این دو بخش در یک جزء متصل قرار دارند.
ورودی
خط اول یک عدد صحیح n است (1 ≤ n ≤ 200 000) — تعداد بخش ها.
i-امین n خط بعدی شامل دو عدد صحیح li و ri است (1 ≤ li < ri ≤ 109) — مختصات انتهای چپ و راست قطعه شماره i. بخش ها به ترتیبی که به خط سفید اضافه شده اند فهرست می شوند.
خروجی
چاپ n عدد صحیح — تعداد اجزای متصل از بخش های سیاه پس از هر افزودن یک قطعه.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3
1 3
4 5
2 4
|
1 2 1 |
| 2 |
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
|
1 2 3 4 5 4 3 2 1 |