Problem
Quando si gioca a un nuovo gioco (un ibrido tra bowling e biliardo), vengono utilizzate N palline, numerate da 1 a N. All'inizio del gioco, queste palline devono essere disposte in linea in ordine numerico. Durante il gioco, il loro ordine potrebbe cambiare.
Per sistemare le palline prima dell'inizio della partita successiva, viene utilizzato il seguente dispositivo. Questo dispositivo è costituito da una testa che, spostandosi sopra le palle, può "succhiare" e "sputare fuori" palloncini. Per avere un'idea migliore di questo dispositivo, immagina un aspirapolvere in grado di aspirare palline, spostarsi nel punto giusto e lì, soffiando nella direzione opposta, "sputare" le palline.
Quando un palloncino viene risucchiato, tutti i palloncini che si trovavano a destra di quello aspirato vengono spostati a sinistra. "Sputare" la pallina può trovarsi tra due palline qualsiasi (e anche prima della prima pallina o dopo l'ultima), poi si inserisce la pallina che sputa tra queste palline, e tutte le palline che si trovano a destra di quella inserita vengono spostate a destra .
È possibile aspirare più di una pallina contemporaneamente nel dispositivo e, quando si sputa la pallina, viene sputata per prima l'ultima pallina aspirata, poi la penultima e così via. (ovvero il dispositivo funziona secondo il principio di uno stack). Le palline vengono sputate una alla volta, ad es. puoi sputare una sola pallina, lasciando il resto all'interno del dispositivo (in questo caso puoi continuare a “sputare” le palline nello stesso punto o in un altro, oppure aspirare nuove palline).
La più energivora delle operazioni descritte è l'operazione di risucchio della palla, quindi vogliamo ridurre al minimo il numero di tali operazioni.
Scrivi un programma che, data la disposizione iniziale delle palline, determini il numero minimo di aspirazioni necessarie per disporre le palline in ordine numerico.
Input
Nel file di input, il numero N è dato per primo — numero di palline (1≤N≤1000). Poi ci sono N numeri che danno i numeri delle palline in ordine da sinistra a destra nella loro posizione attuale (ogni numero — da 1 a N, e ciascuno dei numeri ricorre esattamente una volta nella sequenza).
Uscita
Produci un singolo numero — il numero minimo di operazioni di aspirazione della pallina che saranno necessarie per sistemare le palline nell'ordine del loro numero.
Commenti sui test di esempio
1.Puoi succhiare, ad esempio, il palloncino numero 2 e sputarlo tra il 1° e il 3° palloncino.
2.>Puoi fare qualcosa del genere. Per prima cosa,
succhia il palloncino numero 1, poi – palla numero 2. Quindi ci spostiamo all'inizio e sputiamo la palla prima della 4a palla (questa sarà la palla numero 2). Successivamente, risucchia il palloncino numero 3 e sputalo tra i palloncini 2 e 4. Quindi spostati all'inizio e sputa lì il palloncino numero 1. Tuttavia, questo non è l'unico ordine possibile dei palloncini in questo esempio.
| Input |
Uscita |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Olimpiadi a squadre, Olimpiadi a squadre di Mosca, classi 9-11, 2007, Lega A, Problema F