Maratonci

Možda ste upoznati s nekim od najvećih proslava Nove godine širom svijeta. New York ima poznato spuštanje kugle, Rio de Janeiro ima veličanstveni vatromet na plaži Copacabana, a La Plata ima paljenje lutaka. Manje poznata činjenica je da grad Varaždin ima dugu tradiciju organiziranja ulične utrke koja počinje s glavnog trga točno u ponoć. Vedran je član Turističke zajednice grada Varaždina i želi učiniti sljedeću utrku najposebnijom do sad. Kako bi to postigao, namjerava izgraditi vrlo veliku heksagonalnu rešetku s preprekom postavljenom na svakom vrhu svakog heksagona. Duljina svake prepreke bit će točno polovica veličine stranice svakog heksagona. Tijekom utrke, svaka će prepreka biti poravnata s jednom od strana koje se dodiruju s vrhom na kojem se nalazi. Svi trkači startaju iz istog heksagona i moraju točno slijediti utrku, koja se sastoji od uputa o tome kojim rubom trkači trebaju prijeći kako bi došli do sljedećeg heksagona. Prilikom prelaska nekog heksagonalnog ruba, moguće je da su obje prepreke postavljene na vrhovima te strane poravnate na takav način da potpuno prekrivaju tu stranu. U tom slučaju, trkači će morati preskakati prepreke. Također, ruta utrke bit će takva da trkači neće posjetiti isti heksagon više od jednom. Vedran je već odlučio o ruti utrke i sada želi poravnati prepreke tako da trkači moraju skakati što je više moguće puta.

Ulazni podatci

Prvi redak sadrži cijeli broj N , broj rubova koje trkači moraju prijeći. Drugi redak sadrži N cijelih brojeva x1 , x2 , . . . , xN , koji opisuju rutu utrke. Preciznije, xi opisuje koji rub mora biti prijeđen pri izlasku iz i-tog posjećenog heksagona, koristeći cijeli broj od 1 do 6 koji predstavljaju redom: trebaju li trkači prijeći gornji, gornje-desni, donje-desni, donji, donje-lijevi ili gornje-lijevi rub.

Izlazni podatci

Ispišite broj koji predstavlja najveći broj puta koliko će trkači morati preskakati prepreke ako su optimalno poravnate.

Bodovanje

Podzadatak Bodovi Ograničenja

1 12 1 ≤ N ≤ 20 2 18 1 ≤ N ≤ 1 000 3 30 1 ≤ N ≤ 100 000

Probni primjeri

ulaz ulaz ulaz

5 7 9 1 2 3 4 5 1 3 1 3 3 5 5 6 6 2 3 3 4 4 6 6

izlaz izlaz izlaz 5 4 7

Pojašnjenje prvog probnog primjera: