涂色

题目描述

易书是有名的书画家，但是现在易书厌倦了常规的二维画作（因为他的作品会被人抄袭），然后易书就改变了他的创作风格，将二维的作画风格改为一维的作画风格。易书的最新画作可以用一个长为 $N$（$1 \leq N \leq 300$）的一维数组来描述他的画作，其中每种颜色用 $1\ldots N$ 中的一个整数用来表示。

令易书难受的是，尽管他都这样子做了，她的竞争对手书易现在发现了，如何去抄袭他的一维数组的画作！书易用一种颜色涂在一个区间上，然后等待颜料干了再涂另一个区间，以此类推。书易可以使用 $N$ 中颜色中的每一种任意多次（也可以不用）。

请计算书易抄袭易书的最新的一维画作所需要的涂色的次数。

输入格式

输入的第一行包含 $N$。

下一行包含 $N$ 个范围在 $1 \ldots N$ 之内的整数，表示书易的最新一维画作每个方格上的颜色。

输出格式

输出抄袭这一画作所需要的最小涂色次数。

样例 #1

样例输入 #1

10
1 2 3 4 1 4 3 2 1 6

样例输出 #1

6

提示

样例 1 解释：

在这个样例中，书易可以按下列方式进行涂色。我们用 $0$ 表示一个未涂色的方格。

• 初始时，整个数组均未被涂色：0 0 0 0 0 0 0 0 0 0
• 书易将前九个方格涂上颜色 $1$：1 1 1 1 1 1 1 1 1 0
• 书易在一个区间上涂上颜色 $2$：1 2 2 2 2 2 2 2 1 0
• 书易在一个区间上涂上颜色 $3$：1 2 3 3 3 3 3 2 1 0
• 书易在一个区间上涂上颜色 $4$：1 2 3 4 4 4 3 2 1 0
• 书易在一个方格上涂上颜色 $1$：1 2 3 4 1 4 3 2 1 0
• 书易在最后一个方格上涂上颜色 $6$：1 2 3 4 1 4 3 2 1 6

注意在第一次涂色时，书易可以同时在前九个方格之外将第十个方格也同时涂上颜色 $1$，这并不会影响最后的结果。

测试点性质：

• 对于另外 $15\%$ 的数据，画作中仅出现颜色 $1$ 和 $2$。
• 对于另外 $30\%$ 的数据，对于每一个 $1\le i\le N$，第 $i$ 个方格的颜色在范围 $\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]$ 之内。
• 对于另外 $50\%$ 的数据，没有额外限制。