8260번 - Pająk 다국어

문제

Siedmionogie pająki żyjące w Bajtocji budują pajęczyny o bardzo regularnej strukturze. Pajęczyna taka składa się z węzła centralnego, w którym zazwyczaj odpoczywa pająk, i d kręgów, ponumerowanych liczbami od 1 do d. Każdy krąg to cykl złożony z węzłów połączonych nićmi.

Każdy węzeł, oprócz tych na kręgu d, połączony jest nićmi z siedmioma innymi węzłami. Węzeł centralny jest połączony ze wszystkimi siedmioma węzłami z kręgu 1. Każdy węzeł z kręgu i jest połączony z k ∈ {1, 2} węzłami z kręgu i - 1, dwoma sąsiednimi węzłami z kręgu i oraz l = 5 - k kolejnymi węzłami z kręgu i + 1. Pierwszy i ostatni z tych l węzłów jest połączony z dwoma sąsiednimi węzłami z kręgu i, a pozostałe tylko z jednym. Sieć można zawsze narysować na płaszczyźnie tak, by nici nie przecinały się. Sytuację pokazuje poniższy rysunek.

Sieci takie są bardzo skuteczne. Ostatnio Bajtazar zaobserwował spacer pająka po sieci o d = 10⁹ kręgach. Pająk zaczął w węźle centralnym, a następnie, poruszając się po niciach, wrócił do punktu wyjścia, nie przechodząc przez żaden węzeł więcej niż raz. W każdym węźle we wnętrzu wielokąta, po którego brzegu poruszał się pająk, została złowiona mucha. Bajtazar zanotował sobie kolejne ruchy pająka podczas spaceru i chciałby obliczyć, ile much zostało złapanych.

입력

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (3 ≤ n ≤ 7 777 777) oznaczającą długość spaceru pająka, czyli liczbę odwiedzonych przez niego węzłów.

W drugim wierszu znajduje się ciąg n liczb całkowitych z_i (1 ≤ z_i ≤ 6). Opisuje on kolejne zakręty, jakie wykonywał pająk w trakcie spaceru. Z i-tego węzła na ścieżce pająk wyszedł z_i-tą nicią w kolejności zgodnej z kierunkiem ruchu wskazówek zegara, przy czym za nić 0 uznajemy nić, którą pająk wszedł do węzła. Wartość z₁ dotyczy pierwszego węzła napotkanego po wyjściu z węzła centralnego, zaś z_n opisuje zakręt, jaki musiałby wykonać pająk w węźle centralnym, gdyby chciał przejść całą trasę raz jeszcze.

출력

Twój program powinien wypisać na wyjście jedną liczbę całkowitą - liczbę węzłów sieci wewnątrz wielokąta, który obszedł pająk.

제한

힌트

Wielokąt na rysunku oznacza trasę pająka. We wnętrzu wielokąta znajdują się dwa węzły. Zwróć uwagę, że nie liczymy węzłów na brzegu wielokąta.