Hoofball#10406
In preparazione per il prossimo torneo di hoofball, Farmer John sta allenando le sue mucche (numerate comodamente 1, \ldots, n) nei passaggi della palla. Le mucche sono disposte in una fila molto lunga su un lato del fienile, con la mucca posizionata a x_i unità di distanza dal fienile. Tutte le mucche occupano posizioni distinte.
All'inizio dell'allenamento, Farmer John passerà diverse palle a mucche differenti. Ogni volta che la mucca riceve una palla, sia da Farmer John che da un'altra mucca, la passa alla mucca a lei più vicina. Se diverse mucche si trovano alla stessa distanza da lei, passa la palla alla più a sinistra tra queste. Per dare a ogni mucca almeno un po' di pratica nei passaggi, Farmer John vuole assicurarsi che ogni mucca tenga una palla almeno una volta. Aiutalo a trovare il numero minimo di palle che deve distribuire inizialmente per ottenere questo risultato, supponendo che scelga in modo opportuno l'insieme iniziale di mucche a cui darle.
La prima riga contiene l'intero n~(1 \le n \le 100). La seconda riga contiene interi, dove l'-esimo intero è x_i~(1 \le x_i \le 1000).
Stampa il numero minimo di palle che Farmer John deve inizialmente passare alle mucche affinché ogni mucca tenga una palla almeno una volta.
Nell'esempio, Farmer John dovrebbe passare una palla alla mucca in x = 1 e un'altra palla alla mucca in x = 11. La mucca in x = 1 passa la sua palla alla mucca in x = 3, dopodiché questa palla continua a rimbalzare avanti e indietro tra le mucche in x = 3 e x = 4. La mucca in x = 11 passa la sua palla alla mucca in x = 7, che la passa alla mucca in x = 4, dopodiché anche questa palla continua a rimbalzare tra le mucche in x = 3 e x = 4. Così ogni mucca riceve una palla almeno una volta, sia da Farmer John che da un'altra mucca.
È facile vedere che non esiste una singola mucca a cui Farmer John potrebbe passare una palla in modo che ogni mucca la riceva alla fine.
Esempio 1