Problem
Beyaza boyanmış düz bir çizgi var. n adet siyah parça teker teker eklenir.
Her parça ekleme işleminden sonra bağlı siyah bölümlerin sayısını (birleşimdeki siyah bölümlerin sayısı) belirleyin.
Özellikle, bir parça x noktasında bitiyorsa ve başka bir parça x noktasında başlıyorsa, bu iki parçanın aynı bağlı bileşende olduğunu düşünün.
Giriş
İlk satır bir tamsayıdır n (1 ≤ n ≤ 200 000) — segment sayısı.
sonraki n satırın i'de biri iki tamsayı içerir li ve ri (1 ≤ li < ri ≤ 109) — i numaralı segmentin sol ve sağ uçlarının koordinatları. Segmentler, beyaz çizgiye eklendikleri sırayla listelenir.
Çıktı
n tamsayı yazdır — bir segmentin her eklenmesinden sonra siyah segmentlerden bağlanan bileşenlerin sayısı.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |