接龙数列

题目描述

对于一个长度为 K 的整数数列：$A_1, A_2, . . . , A_K$，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i−1}$ 的末位数字 $(2 ≤ i ≤ K)$。 例如 $12, 23, 35, 56, 61, 11$ 是接龙数列；$12, 23, 34, 56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。所有长度为 $1$ 的整数数列都是接龙数列。 现在给定一个长度为 $N$ 的数列 $A_1, A_2, . . . , A_N$，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1, A_2, . . . , A_N$。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

5
11 121 22 12 2023

样例输出 #1

1

提示

删除 $22$，剩余 $11, 121, 12, 2023$ 是接龙数列。

对于 $20\%$ 的数据，$1 ≤ N ≤ 20$。 对于 $50\%$ 的数据，$1 ≤ N ≤ 10000$。 对于 $100\%$ 的数据，$1 ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^9$。所有 $A_i$ 保证不包含前导 $0$。