Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: masyvas78.in

Rezultatų failas: masyvas78.out

Jei norite pateikti savo sprendimą - prisijunkite.

Taipogi masyvas

Vytas turi masyvą sudarytą iš n skaičių. Vytas nusprendė su šiuo masyvo pažaisti. Žaidimo taisyklės tokios:

Žaidimas susideda iš n ėjimų. Kiekvieno ėjimo metu Vytas pasirenka vieną masyvo elementą ir jį ištrina. Už tai jis gauna min(a,b) taškų kur a ir b žymi šalia ištrinto elemento buvusius gretimus skaičius. Jei ištrintas elementas turėjo mažiau nei du gretimus skaičius, Vytas taškų negauna. Žaidimas baigiasi, kai masyve elementų nebelieka.

Ištrynus elementą, abi masyvo dalys yra suklijuojamos ir Vytas žaidžia toliau. Padėkite Vytui išsiaiškinti, kiek maksimaliai taškų jis gali surinkti.

Pradiniai duomenys

Pirmoje eilutėje duotas vienas skaičius n (1\\leqn\\leq5*10^5) - masyvo dydis.

Antroje eilutėje duota n skaičių a_i (1\\leqa_i\\leq10^6) - masyvo elementai.

Rezultatai

Išveskite vieną skaičių - maksimalų taškų kiekį.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
1 2 3 4 5
 
6