Fișierul intrare/ieșire	game.in, game.out	Sursă	Concurs Shumen juniori 2017
Autor	autor necunoscut	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.15 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Game

Boyan se joacă un joc pe calculator. La început există N bile așezate în linie. Pe fiecare bilă este scris un număr și pe oricare două bile vecine sunt numere diferite. Jocul are următorii pași:

1. Jucătorul șterge o bilă dintre cele date.
2. Cât timp există bile consecutive cu același număr, acestea sunt automat șterse din linie.
3. Dacă mai rămân bile, se merge la pasul 1, altfel jocul se termină.

Scorul este numărul total de bile șterse automat.
Scopul este să se maximizeze scorul.

Să considerăm un exemplu cu 6 bile, numerotate {1, 2, 3, 2, 1, 5}.
1. Boyan șterge bila cu numărul 3.
Bilele rămare sunt: {1, 2, 2, 1, 5}.
2. Ștergând bilele vecine pe care este scrisă aceeași valoare, avem:
{1, 2, 2, 1, 5} -> {1, 1, 5} -> {5}.
Bila rămasă este {5}.
3. Mai rămân bile, deci se merge la pasul 1.

1. Boyan șterge bila cu numărul 5.
Bilele rămase: {}.
2. Nu sunt bile vecine pe care este scris acela și număr.
3. Nu mai sunt bile rămase, deci se termină jocul.

Numărul de bile șterse automat este 4.
Acesta este scorul maxim posibil pentru acest joc.
Boyan este un jucător bun, dar nu este sigur că joacă mereu optim.
Scrieți un program care să îl ajute să obțină cel mai mare scor.

Date de intrare

Fișierul de intrare game.in conține pe prima linie un întreg pozitiv N.
Pe a doua linie conține N întregi pozitivi reprezentând numerele scrise pe bile.

Date de ieșire

În fișierul de ieșire game.out se va afișa scorul maxim pe care Boyan îl poate obține.

Restricții

• 1 ≤ N ≤ 500
• 1 ≤ numărul scris pe o bilă ≤ 1 000 000
• În 20% dintre teste N ≤ 10
• În 50% dintre teste N ≤ 100

Exemplu

Explicație

...