Turbo

Ο Frane έχει το καθήκον να ταξινομήσει έναν πίνακα αριθμών. Ο πίνακας αποτελείται από N ακέραιους, ο καθένας μεταξύ ~1~ και ~N~ (συμπεριλαμβανομένων), με καθένα από αυτούς να εμφανίζεται ακριβώς μία φορά στον πίνακα. Ο Frane ανέβηκε με τον ακόλουθο αλγόριθμο ταξινόμησης που λειτουργεί σε ~N~ φάσεις και τον ονόμασε turbosort:

• Στην πρώτη φάση, ο αριθμός ~1~ μετακινείται στη θέση ~1~ με επανειλημμένη εναλλαγή διαδοχικών στοιχείων.
• Στη δεύτερη φάση, ο αριθμός ~N~ μετακινείται στη θέση ~N~ με τον ίδιο τρόπο.
• Στην τρίτη φάση, ο αριθμός ~2~ μετακινείται στη θέση ~2~.
• Στην τέταρτη φάση, ο αριθμός ~N - 1~ μετακινείται στη θέση ~N - 1~.
• Και ούτω καθεξής.

Με άλλα λόγια, όταν ο αριθμός της φάσης είναι περιττός, ο Frane θα επιλέξει τον μικρότερο αριθμό που δεν έχει ακόμη επιλέξει και θα τον μετακινήσει στην τελική του θέση. Σε ζυγές φάσεις επιλέγει τον μεγαλύτερο αριθμό που δεν έχει ακόμη επιλέξει.
Γράψτε ένα πρόγραμμα το οποίο, δεδομένου του αρχικού πίνακα, θα τυπώνει τον αριθμό των αντιμεταθέσεων σε κάθε φάση του αλγορίθμου.

Είσοδος

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

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις αξίας του ~70~% των συνολικών πόντων, το ~N~ θα είναι μικρότερο του ~100~.

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

input

3
2
1
3

output

1
0
0

input

5
5
4
3
2
1

output

4
3
2
1
0

input

7
5
4
3
7
1
2
6

output

4
2
3
0
2
1
0