Zenyk and happy cafes

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk decided to take up the architecture of Lviv. He wants to place several cafes and connect them with roads. Each road will have a label: either 4 or 7. Roads can be traversed in both directions. No pair of cafes can be directly connected by more than one road.

Zenyk wants his cafe network to be happy. This means that there is a happy route in it. A route is called happy if it traverses roads with labels that form a given sequence \(a\) of digits 4 and 7 (for example, 477447). During the route, it is allowed to visit the same cafe multiple times.

What is the minimum number of cafes \(k\) Zenyk needs so that such a happy cafe network exists?

Input

The first line contains a single integer \(n\) — the length of the sequence \(a\).

The second line contains \(n\) numbers \(a_1, a_2, \ldots, a_n\) — the sequence of labels in the happy route.

Output

In a single line, output a single number \(k\), denoting the minimum number of cafes for the network to be happy.

Constraints

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

\(a_i = \texttt{4}\) or \(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

In the first example, 2 cafes are enough, with a road labeled 4 between them. Then the path \(1 \xrightarrow{4} 2 \xrightarrow{4} 1 \xrightarrow{4} 2\) will be happy.

In the second example, 3 cafes are needed as shown in the image below. Then the path \(3 \xrightarrow{7} 2 \xrightarrow{7} 1 \xrightarrow{4} 3 \xrightarrow{4} 1 \xrightarrow{7} 2\) will be happy.

It can be proven that in the third example, at least 4 cafes are needed. A happy path for the image below is \(1 \xrightarrow{4} 2 \xrightarrow{7} 3 \xrightarrow{4} 4 \xrightarrow{7} 1 \xrightarrow{4} 2 \xrightarrow{7} 3\).