题目内容

一位粉刷匠准备为一排连续的 $N$ 个格子喷涂颜色。初始时所有格子都是空白的。每次操作，他可以选择一个区间 $[L, R]$，并将该区间内的所有格子喷涂成同一种颜色。给定最终希望得到的目标颜色序列 $C_1, C_2, \dots, C_N$，请问最少需要多少次操作才能将所有格子变成目标颜色？

约束：格子数量 $N$ 不超过 400，每个颜色编号均为不超过 $N$ 的正整数。

输入描述

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数，依次表示 $C_1, C_2, \dots, C_N$，相邻整数之间用一个空格分隔。

输出描述

输出一个整数，表示最少需要的操作次数。

样例1

输入

5
1 2 1 2 1

输出

5

说明

颜色序列没有相邻相同的情况，压缩后仍为 1 2 1 2 1。因为任何两个同色的位置之间都隔着不同颜色，无法通过一次操作同时涂色而不影响中间的格子，所以必须逐个涂色，最少操作次数为 5。

样例2

输入

6
1 2 2 1 1 2

输出

4

说明

压缩相邻相同颜色后得到序列 1 2 1 2。这是一个交替序列，首尾颜色不同，无法合并，最少需要 4 次操作。

样例3

输入

1
5

输出

1

说明

只有一个格子，只需一次操作涂成目标颜色 5，这是边界情况。

样例4

输入

7
3 3 1 2 2 1 3

输出

3

说明

压缩后序列为 3 1 2 1 3。可以发现首尾都是 3，可以先将整个区间涂成 3（1 次），然后再处理中间部分 1 2 1。将 1 2 1 涂好最少需要 2 次（先全部涂 1，再将中间涂 2），因此总操作次数为 $1 + 2 = 3$。