Carta Alta Carta Bassa#11160
Bessie e la sua amica Elsie stanno ora giocando a un semplice gioco di carte. Prendono un mazzo di carte, numerate da a , e le dividono equamente, in modo che ogni giocatrice riceva carte. Poi giocano turni, in ciascuno dei quali ogni giocatrice gioca una carta.
Nei primi turni, la giocatrice che gioca la carta di valore più alto ottiene un punto. Nei restanti turni, le regole cambiano: il punto va alla giocatrice che gioca la carta di valore più basso.
Poiché Bessie riesce a prevedere l'ordine in cui Elsie giocherà le proprie carte, determina il numero massimo di punti che Bessie può ottenere.
La prima riga contiene un intero n~(2 \le n \le 50000), ed è garantito che sia pari.
Le successive righe contengono le carte che Elsie giocherà in ciascuno dei turni consecutivi. Si noti che da questa informazione è possibile determinare le carte di Bessie.
Stampa un singolo intero, ovvero il numero massimo di punti che Bessie può ottenere.
In questo esempio, Bessie ha in mano le carte e . Può usare queste carte per ottenere al massimo punti, conservando la carta per uno dei turni della seconda metà della partita.
Esempio 1