#1127. 【NFLSPC #4】Rebalance

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

有 $n$ 个蒟蒻,每个蒟蒻都有一个崇拜的神犇。现在这些蒟蒻排成了一排,并从左至右依次编号为 $1,2,\cdots,n$。

我们定义 区间 $[l,r]$,为编号介于 $[l,r]$ 之间的蒟蒻形成的集合。我们定义区间的长度为这个集合的大小,即区间 $[l,r]$ 的长度为 $r-l+1$。

对于一个区间 $[l,r]$,如果代表的集合中,存在严格大于 $\frac{r-l+1}{2}$(即区间长度的一半)个蒟蒻都崇拜同一个神犇,并且区间的长度不为 $1$,那么我们称这个区间为 不平衡 的。我们称一个区间是 平衡 的,当且仅当他不是不平衡的。

请你求出最少能划分成几个区间,使得每个区间都是平衡的。


输入格式

第一行一个正整数 $n$。

第二行 $n$ 个空格正整数。其中第 $i$ 个数即编号为 $i$ 的蒟蒻崇拜的神犇的编号。保证神犇的编号介于 $1$ 到 $n$ 之间。

输出格式

输出一行,包含一个整数,为最少的区间数目。


样例一

input

3
1 1 1

output

3

样例二

input

4
1 1 2 2

output

1

限制与约定

  • 子任务 $1$($100$ 分):$2\le n\le 10^6$,每个蒟蒻崇拜的神犇的编号都介于 $1$ 到 $n$ 之间。

$by\ \text{skyline}$