Zadanie

Factum fieri infectum non potest

Počet bodov: 40, časový limit: 1000ms

Kubík po dlhoročnom spojenom štúdiu Alchýmie a Informatiky prišiel na zbrusu nový obor - Xorchýmiu. Teda alchýmia za pomoci bitovej operácie xor.

Na obhajobu svojej bakalárky dostal za úlohu predviesť, ako užitočná je táto schopnosť.

Jeho oponent Žaba doniesol na obhajobu \(n\) kôpok základných prvkov.

Alchýmia sa zaoberá menením všetkého na zlato. Vie niečo podobné aj táto tvoja paveda, čo si si vymyslel, Xorchýmia? Zaútočil Žaba na Kubíkovu bakalárku.

Pomôžte Kubíkovi predviesť moc Xorchýmie!

Úloha

Na stole pred Kubíkom je rozložených \(n\) kôpok základných prvkov. V obore Xorchýmie si ich vieme reprezentovať celými číslami od \(1\) do \(5\).

V jednom kroku vie Kubík zobrať dve kôpky \(x\) a \(y\), a pomocou Xorchýmie dostať jednu kôpku prvku \(x \oplus y\). Aby však boli prvky počas celého procesu bezpečné, Kubík nevykoná Xorchýmiu na kôpkach ktoré by vyprodukovali prvok mimo intervalu \([1,5]\).

Zistite, koľko najviac kôpok ľubovoľného jedného prvku vie Kubík dosiahnuť.

Pripomienka: bitová operácia xor, \(\oplus\), funguje tak že \(i\)-ty bit je \(1\) vo výsledku \(x \oplus y\) práve vtedy, keď je \(1\) v \(x\) alebo \(y\), ale nie súčasne.

Vstup a výstup

V prvom riadku je číslo \(n\) – počet kôpok. V druhom riadku je \(n\) celých čísel \(p_i\) – typ prvku v \(i\)-tej kôpke.

Platí \(1 \leq p_i \leq 5\). V druhej sade \(1 \leq p_i \leq 3\).

V prvej sade \(1 \leq n \leq 8\). V druhej a tretej \(1 \leq n \leq 1\,000\).

Príklady

Input:

4
3 1 2 2

Output:

3

Kubík vie vyxorovať \(3 \oplus 1 = 2\), a získať tak 3 kôpky prvku 2.

Input:

5
4 5 2 3 3

Output:

3

Tu vie Kubík naxorovať tri trojky.

Pre odovzdávanie sa musíš prihlásiť.