Fuori posto#10419
Il contadino John si sente ambizioso. Vuole tentare qualcosa che non sembra mai riuscire del tutto: fotografare la sua intera mandria di mucche.
Affinché la fotografia venga bene, chiede alle mucche di disporsi in un'unica fila dalla più bassa alla più alta. Purtroppo, subito dopo che è riuscito a metterle in fila, la mucca Bessie — la solita combinaguai — esce dalla fila e si reinserisce in una posizione diversa!
Ora il contadino John vuole scambiare coppie di mucche in modo che l'intera mandria sia di nuovo disposta correttamente, dalla più bassa alla più alta. Aiutatelo a determinare il numero minimo di scambi necessari per ripristinare l'ordine corretto. Le mucche scambiate non devono essere necessariamente adiacenti.
La prima riga contiene un numero intero n~(2 \le n \le 100), il numero di mucche. Ognuna delle successive righe contiene un solo numero intero: l'altezza di una mucca nella fila attuale, dopo che Bessie ha cambiato posizione. Ogni altezza è un numero intero compreso tra e 10^6. Più mucche possono avere la stessa altezza.
Stampare un solo numero intero: il numero minimo di scambi che il contadino John deve effettuare per riportare la fila in ordine crescente.
Nell'esempio seguente, Bessie è chiaramente la mucca di altezza . Il contadino John riporta le mucche in ordine crescente con tre scambi, come mostrato di seguito:
2~4~7~7~9~3 — la fila iniziale
2~4~7~7~3~9 — si scambiano le ultime due mucche
2~4~3~7~7~9 — si scambiano il primo e il
2~3~4~7~7~9 — si scambiano il e il
Esempio 1