Minimum Deletions for Chain Sequence

Given a sequence of N integers: \(A_1, A_2, \ldots, A_N\), we call a sequence a chain sequence if and only if for every index \(i\) (\(2 \le i \le N\)), the first digit of \(A_i\) is equal to the last digit of \(A_{i-1}\). Note that any sequence of length 1 is considered a chain sequence.

For example, the sequence 12 23 35 56 61 11 is a chain sequence because:

• Last digit of 12 is 2 and first digit of 23 is 2.
• Last digit of 23 is 3 and first digit of 35 is 3.
• Last digit of 35 is 5 and first digit of 56 is 5.
• Last digit of 56 is 6 and first digit of 61 is 6.
• Last digit of 61 is 1 and first digit of 11 is 1.

However, the sequence 12 23 34 56 is not a chain sequence, because the last digit of 34 is 4, which does not match the first digit of 56 (which is 5).

Your task is to determine the minimum number of elements that need to be removed from the given sequence so that the remaining sequence (keeping the original order) becomes a chain sequence.

Input Constraints: The first line contains an integer \(N\) representing the length of the sequence, followed by a line of \(N\) integers.

Output: Print a single integer representing the minimum number of deletions needed.

inputFormat

The first line contains an integer \(N\) (the number of elements in the sequence). The second line contains \(N\) space-separated integers \(A_1, A_2, \ldots, A_N\).

outputFormat

Output a single integer representing the minimum number of deletions required to transform the sequence into a chain sequence.

sample

6
12 23 35 56 61 11

0