题目描述

小红给了小苯一个长为 n 的数组 a，初始数组中的每个数字都是白色。小苯可以进行如下两种操作中的一种：

1. 任选一个白色的元素，将其染红。
2. 选择一个区间[l, r]，满足al != ar且区间两个端点元素均为白色。将区间所有元素染红。

小苯想知道他最少几次操作可以将所有数字都染红，请你帮帮他吧。

输入描述

对于每组测试数据，输入包含两行。

第一行一个正整数 n (1 <= n <= 3000)，表示数组 a 的长度。

第二行 n 个正整数 ai (1 <= ai <= 109)，表示数组 ai 的元素。

输出描述

输出包含一行一个正整数，表示染红所有数字的最小操作次数。

输入示例

3
1 2 1

输出示例

2

提示信息

先选择第一和第二个数进行一次区间染色，再选择第三个数染色。一共两次。

时间限制：c/c++：1s；java/go：4s；其他语言：6s。