Зеник і щасливі кафе

Limits: 2 sec., 512 MiB

Зеник вирішив зайнятися архітектурою Львова. Він хоче розмістити кілька кафе та з’єднати їх дорогами. Кожна дорога матиме позначку: або 4, або 7. Дороги можна проходити в обидва боки. Жодна пара кафе не може бути безпосередньо з’єднана більше ніж однією дорогою.

Зеник хоче, щоб його мережа кафе була щасливою. Це означає, що в ній існує щасливий маршрут. Маршрут називається щасливим, якщо він проходить по дорогах з позначками, що утворюють задану послідовність \(a\) з цифр 4 і 7 (наприклад, 477447). Під час маршруту можна кілька разів повертатися в те саме кафе.

Яка найменша кількість кафе \(k\) потрібна Зенику, щоб така щаслива мережа кафе існувала?

Input

В першому рядку задано одне ціле число \(n\) — довжина послідовності \(a\).

У другому рядку задано \(n\) чисел \(a_1, a_2, \ldots, a_n\) — послідовність позначок в щасливому маршруті.

Output

В єдиному рядку виведіть одне число \(k\), що позначає мінімальну кількість кафе, щоб мережа була щасливою.

Constraints

\(1 \le n \le 10^{5}\),

\(a_i = \texttt{4}\) або \(a_i = \texttt{7}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 4 4	2

Input (stdin) сopy	Output (stdout) сopy
5 7 7 4 4 7	3

Input (stdin) сopy	Output (stdout) сopy
6 4 7 4 7 4 7	4

Input (stdin) сopy	Output (stdout) сopy
10 4 7 7 4 4 7 4 4 7 4	3

Notes

В першому прикладі достатньо 2 кафе, між якими буде дорога з позначкою 4. Тоді щасливим буде шлях \(1 \xrightarrow{4} 2 \xrightarrow{4} 1 \xrightarrow{4} 2\).

В другому прикладі необхідно 3 кафе як на зображенні нижче. Тоді щасливим буде шлях \(3 \xrightarrow{7} 2 \xrightarrow{7} 1 \xrightarrow{4} 3 \xrightarrow{4} 1 \xrightarrow{7} 2\).

Можна довести, що в третьому прикладі необхідно як мінімум 4 кафе. Щасливий шлях для зображення нижче \(1 \xrightarrow{4} 2 \xrightarrow{7} 3 \xrightarrow{4} 4 \xrightarrow{7} 1 \xrightarrow{4} 2 \xrightarrow{7} 3\).