Bst

Ένα δυαδικό δέντρο αναζήτησης είναι ένα δέντρο στο οποίο κάθε κόμβος έχει το πολύ δύο κόμβους-παιδιά (ένα αριστερό και ένα δεξιό παιδί-υποδέντρο). Κάθε κόμβος έχει έναν ακέραιο γραμμένο μέσα του. Εάν ο αριθμός ~X~ είναι γραμμένος μέσα σε έναν κόμβο, τότε οι αριθμοί στο αριστερό υποδέντρο του είναι μικρότεροι από το ~X~ και οι αριθμοί στο δεξί του υποδέντρο είναι μεγαλύτεροι από το ~X~.
Θα σας δοθεί μια ακολουθία ακεραίων μεταξύ ~1~ και ~N~ (κλειστό διάστημα ~[1,\;N]~) έτσι ώστε κάθε αριθμός να εμφανίζεται στην ακολουθία ακριβώς μια φορά. Πρέπει να δημιουργήσετε ένα δυαδικό δέντρο αναζήτησης από την ακολουθία, βάζοντας τον πρώτο αριθμό στον κόμβο-ρίζα και εισάγοντας κάθε άλλο αριθμό με τη σειρά. Με άλλα λόγια, εκτελέστε το insert(~X~, ρίζα) για κάθε άλλο αριθμό:
insert (αριθμός ~X~, κόμβος ~N~ )
 αυξήστε τον μετρητή ~C~ κατά ~1~
 αν ο ~X~ είναι μικρότερος από τον αριθμό στον κόμβο ~N~
  αν ο ~N~ δεν έχει αριστερό παιδί
   δημιουργήστε έναν νέο κόμβο με τον αριθμό ~X~ και ορίστε τον ως το αριστερό παιδί του κόμβου ~N~
  αλλιώς
   insert(~X~, αριστερό παιδί του κόμβου ~N~)
 αλλιώς (ο ~X~ είναι μεγαλύτερος από τον αριθμό στον κόμβο ~N~)
  αν ο ~N~ δεν έχει δεξί παιδί
   δημιουργήστε έναν νέο κόμβο με τον αριθμό ~X~ και ορίστε τον ως το δεξί παιδί του κόμβου ~N~
  αλλιώς
   insert(~X~, δεξί παιδί του κόμβου ~N~)
Γράψτε ένα πρόγραμμα που να υπολογίζει την τιμή του μετρητή ~C~ μετά από κάθε εισαγωγή αριθμού. Ο μετρητής είναι αρχικά ~0~.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N (1 \le N \le 300\,000)~, το μήκος της ακολουθίας.
Οι υπόλοιπες ~N~ γραμμές περιέχουν τους αριθμούς στην ακολουθία, ακέραιους στο διάστημα ~[1, N]~. Οι αριθμοί θα είναι διακριτοί.

Έξοδος

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

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~50%~ των πόντων, το ~N~ θα είναι το πολύ ~1\,000~.

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

input

4
1
2
3
4

output

0
1
3
6

input

5
3
2
4
1
5

output

0
1
2
4
6

input

8
3
5
1
6
8
7
2
4

output

0
1
2
4
7
11
13
15