Codah ClubTrain. Submit. Improve.
Sign in
English
#0002A2

Turbo

Frane je dobio zadatak da uzlazno sortira niz brojeva. Niz se sastoji od N prirodnih brojeva, a svaki prirodni broj između 1 i N se točno jednom nalazi u nizu. Frane je smislio sljedeći algoritam za sortiranje, te ga je nazvao turbosort: Algoritam se provodi u N faza. U prvoj fazi se broj 1 nizom zamjena susjednih elemenata dovodi na poziciju 1. U drugoj fazi se broj N nizom zamjena susjednih elemenata dovodi na poziciju N. U trećoj fazi se broj 2 nizom zamjena susjednih elemenata dovodi na poziciju 2. U četvrtoj fazi se broj N-1 nizom zamjena susjednih elemenata dovodi na poziciju N-1. Drugim riječima: Frane u neparnim fazama odabire najmanji dosad neodabrani broj, te ga dovodi na njegovu konačnu poziciju, dok u parnim fazama odabire najveći dosad neodabrani broj. Napišite program koji za zadani niz ispisuje broj zamjena susjednih elemenata u svakoj fazi izvođenja
algoritma.


InputU prvom retku nalazi se prirodni broj N (1 ≤ N ≤ 100 000), broj elemenata niza. U sljedećih N redaka nalazi se po jedan prirodni broj. Ti brojevi predstavljaju elemente niza kojeg treba sortirati. Brojevi će biti između 1 i N (uključivo), te se neće ponavljati.

OutputZa svaku od N faza potrebno je ispisati redak koji sadrži broj zamjena susjednih elemenata u toj fazi.


Ulaz

3
2
1
3

Izlaz

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

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.