题目背景

PA 2024 1B

题目描述

题目译自 PA 2024 Runda 1 Liderzy

根据 PWN 字典（一本波兰语字典），「lider」是指「政党、工会或其他社会组织的领导人」。另一方面，在算法中，序列中出现次数严格大于序列长度一半的元素被称为序列的领导元素。例如，序列 $[7, 2, 5, 7, 7]$ 的领导元素是数字 $7$，而序列 $[2, 3, 2, 3]$ 则没有领导元素。

在本题中，我们将重点讨论「lider」一词的后一种含义。给定一个数列，你的任务是将它分成最小数目的数列（不一定连续），满足每个数列都有一个领导元素，并输出这个最小数目。可以证明这样的划分总是可能的。

输入格式

第一行一个整数 $n\ (1\le n\le 500\,000)$，表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le n)$，表示这个序列。

输出格式

输出一行一个整数表示答案。

5
1 2 3 1 2

2

提示

输入的序列可以划分为 $[1,3,1]$ 和 $[2,2]$，这样划分后的两个序列就都有领导元素了（分别为 $1$ 和 $2$）。