Problem Description

For an integer sequence of length $K$: $A_{1}, A_{2}, \ldots, A_{K}$, we call it a chain sequence if and only if the first digit of $A_{i}$ is exactly equal to the last digit of $A_{i-1}$ ($2 \leq i \leq K$).

For example, $12, 23, 35, 56, 61, 11$ is a chain sequence; $12, 23, 34, 56$ is not a chain sequence, because the first digit of $56$ is not equal to the last digit of $34$. All integer sequences of length $1$ are chain sequences.

Now you are given a sequence of length $N$: $A_{1}, A_{2}, \ldots, A_{N}$. Please compute the minimum number of elements to delete so that the remaining sequence becomes a chain sequence.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_{1}, A_{2}, \ldots, A_{N}$.

Output Format

Output one integer representing the answer.

5
11 121 22 12 2023

1

Hint

Sample Explanation

Delete $22$, and the remaining $11, 121, 12, 2023$ is a chain sequence.

Constraints

For $20\%$ of the testdata, $1 \leq N \leq 20$.

For $50\%$ of the testdata, $1 \leq N \leq 10^{4}$.

For $100\%$ of the testdata, $1 \leq N \leq 10^{5}$, $1 \leq A_{i} \leq 10^{9}$. All $A_{i}$ are guaranteed to have no leading zeros.

Lanqiao Cup 2023 Provincial Contest Group B, Problem E.

Translated by ChatGPT 5