RIG şi LEF, doi corbi inteligenţi, se joacă veseli pe un gard format din N scânduri de înălţimi h[1], h[2], h[3], ..., h[N]. Gardul este puţin cam ciudat, nu găseşti în el două scânduri la fel de înalte. La începutul fiecărui joc cei doi corbi pornesc de pe aceeaşi scândură şi, pe rând, RIG se mută spre dreapta pe o scândură mai joasă decât a lui LEF şi aşteaptă să mute LEF, iar LEF se mută spre stânga pe o scândură mai joasă decât a lui RIG şi îl aşteaptă pe RIG. Jocul se opreşte când nu se mai pot efectua mutări. Prima mutare o poate face RIG sau LEF, hotărâre luată de comun acord.
Cerinţă
Scrieţi un program care să determine numărul maxim de mutări pe care le pot face RIG şi LEF în total în cadrul unui singur joc pe un gard cu N scânduri de înălţimi numere naturale distincte precizate.
Date de intrare
Fişierul de intrare riglef.in conţine pe prima linie numărul natural N, iar pe linia a doua N numere naturale care reprezintă înălţimile scândurilor din gard cu proprietatea din enunţ, termenii fiind separaţi prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire riglef.out va conţine o singură linie pe care va fi scris numărul cerut.
Restricţii
2 <= N <= 1000
1 <= h[i] <= 100 000, 1<=i<=N
Exemple
riglef.in
riglef.out
Explicaţie
6
12 35 18 47 45 21
4
Jocul porneşte de pe scândura de înălţime 47şi RIG mută la 45, LEF mută pe 35, RIG mută pe 21, LEF mută pe 12, apoi jocul se opreşte.