题目为ICPC Kunming 2020 C, Cities。

简要题意：

现有 $N$ 个城镇和 $N$ 个国王，刚开始第 $i$ 个城镇属于第 $a_i$ 个国王。 现在每次可以选一个下标连续且属于同意国王的城镇，将这些城镇归属到任意一个国王下面，问让所有城镇都属于一个国王，最少需要多少次这样的操作。

$n\le5000$, 每个数出现不超过 $15$ 次。

这题可不可以用贪心：

1. 不考虑边缘的区间，选最长连续区间，如果最近的两端（不一定挨着）有同一个国王，就给这个国王。若有多个区间满足条件，从左到右依次做。
2. 当任何区间两端（不一定挨着）都没有同一国王时，从左到右依次合并。

这样的做法靠谱吗？求hack，急qwq