Cjvetici

Σε έναν μακρινό πλανήτη, μπορούν να βρεθούν παράξενα φυτά με δύο βλαστούς. Κάθε φυτό στον πλανήτη μπορεί να περιγραφεί με τρεις αριθμούς: τις συντεταγμένες ~x~ των βλαστών ~L~ και ~R~, και το ύψος ~H~ στο οποίο οι βλαστοί συνδέονται. Η εικόνα απεικονίζει ένα φυτό με ~L = 2~, ~R = 5~ και ~H = 4~.

Κάθε μέρα ένα νέο φυτό φυτρώνει στον πλανήτη. Το φυτό που φυτρώνει την \(1^{η}\) ημέρα έχει ύψος ~1~, και κάθε επόμενο φυτό είναι υψηλότερο από το προηγούμενο κατά ένα.

Όταν ένας βλαστός ενός νέου φυτού διασταυρώνεται με το οριζόντιο τμήμα ενός άλλου φυτού, αναπτύσσεται ένα μικρό λουλούδι (αν δεν υπήρχε ήδη ένα εκεί). Εάν τα τμήματα αγγίζουν απλώς ένα σημείο, ένα λουλούδι δεν θα αναπτυχθεί εκεί.

Οι παρακάτω εικόνες αποτελούν απεικόνιση του πρώτου παραδείγματος.

Γράψτε ένα πρόγραμμα που, λαμβάνοντας υπόψη τις συντεταγμένες όλων των φυτών, να υπολογίζει κάθε ημέρα τον αριθμό των νέων λουλουδιών.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~ ~(1 \le N \le 100\,000)~, τον αριθμό των ημερών.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~L~ και ~R (1 \le L < R \le 100\,000)~, τις συντεταγμένες του βλαστού ενός φυτού.

Έξοδος

Τυπώστε ~N~ γραμμές, τον αριθμό των νέων λουλουδιών μετά από κάθε φυτό που μεγάλωσε.

Παραδείγματα

input

4
1 4
3 7
1 6
2 6

output

0
1
1
2

input

5
1 3
3 5
3 9
2 4
3 8

output

0
0
0
3
2