题目描述

给你一串数字。我们把某个数字在一串里出现次数超过一半，叫做这串的“主数”。

现在要把原串分成尽量少的子串（可以从原串里按顺序挑元素拼成，元素不要求相邻，但每个元素只能用一次），并且每个子串都要有主数。请输出最少能分成的子串数。可以保证一定能分成。

输入格式

第一行：一个整数 $n$。 第二行：$n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行，一个整数，表示最少的子串个数。

输入输出样例 #1

输入 #1

5
1 2 3 1 2

输出 #1

2

样例1解释

一种划分：$[1,3,1]$ 和 $[2,2]$，它们的主数分别是 $1$ 和 $2$。

说明/提示

数据范围

对于30%的数据：$1 \le n \le 5000$；$1 \le a_i \le n$

对于100%的数据：$1 \le n \le 5\times 10^5$；$1 \le a_i \le n$