Carta alta carta bassa (Platino)#11164
Bessie e la sua amica Elsie stanno ora giocando a un semplice gioco di carte. Prendono un mazzo di carte, numerate da a , e lo dividono equamente, in modo che ogni giocatore riceva carte. Successivamente giocano round, in ciascuno dei quali Bessie ed Elsie mettono in gioco una carta ciascuna.
Inizialmente, il giocatore che gioca la carta con il numero più alto ottiene un punto. Tuttavia, in un qualsiasi momento della partita, Bessie può decidere di cambiare le regole in modo che, fino alla fine della partita, il punto venga assegnato al giocatore che gioca la carta con il numero più basso. Bessie può anche scegliere di non usare questa possibilità, lasciando che l'intera partita si svolga secondo la regola "vince la carta più alta", oppure può cambiare le regole immediatamente, facendo sì che l'intera partita si svolga secondo la regola "vince la carta più bassa".
Poiché Bessie conosce l'ordine in cui Elsie giocherà le sue carte, determinate il numero massimo di punti che Bessie può ottenere.
Nella prima riga è contenuto un numero intero n~(2 \le n \le 50000).
Nelle successive righe sono contenute le carte che Elsie giocherà in ciascuno dei round consecutivi della partita. Si noti che da queste informazioni è possibile determinare le carte di Bessie.
Stampate il numero massimo di punti che Bessie può ottenere.
In questo esempio, Bessie ha in mano le carte e , e può ottenere al massimo punti. Ad esempio, Bessie può attenersi alla regola "vince la carta più alta" per tutta la partita. Può battere la carta con la sua carta , perdere contro la carta giocando , e poi battere le carte e giocando rispettivamente e , ottenendo un totale di punti.
Esempio 1