E. Colorful Corgis
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Corgi Adoption Center has an adorable selection of corgis with various fur color combinations. Today is adoption day, and they want all of the corgis to be taken home to a loving home. They have gathered them all in a circle to show them all off to their potential new owners. The center has noticed in the past, that no owner likes to have more than 2 distinct fur colors (among their own corgis) in total. Furthermore, in the circle, the corgis are placed next to their friends, and the adoption center wants to avoid separating friends too much. So every individual can adopt a single contiguous segment of the circle. What is the minimum number of compassionate individuals the center needs to guarantee that all corgis are adopted?

Input

The first line will contain a single integer $$$N\ (1 \leq N \leq 10^6)$$$ indicating how many corgis are in the circle. The following $$$N$$$ lines will each contain 1 or 2 lowercase letters indicating the fur colors of each corgi. Note: The $$$n$$$th corgi is next to the $$$1$$$st in the circle.

Output

The output is a single integer indicating the minimum number of individuals needed to adopt all the corgis.

Examples
Input
7
a
b
ab
b
c
d
c
Output
2
Input
6
a
c
d
c
a
b
Output
2
Note

Sample 1:

One person can adopt Corgis 1 - 4 since this has a total of 2 colors: a, b. A second person can adopt Corgis 5 - 7 since this has a total of 2 colors: c, d. Thus, 2 people are needed minimum.

Sample 2:

One person can adopt Corgis 1, 5, and 6 (since the circle wraps around) since this has the 2 colors: a, b. A second person can adopt Corgis 2, 3, and 4 since this has a total of 2 colors: c, d. Thus, 2 people are needed.