Согласно словарю PWN, «лидер» — это, среди прочего, «руководитель политической партии, профсоюза или других общественных организаций». В алгоритмике же лидером последовательности элементов называют элемент, количество вхождений которого строго больше половины длины последовательности. Например, лидером последовательности $[7, 2, 5, 7, 7]$ является число $7$, а последовательность $[2, 3, 2, 3]$ вообще не имеет лидера.
В этой задаче мы сосредоточимся на втором значении слова «лидер». Имея заданную последовательность чисел, ваша задача — разбить её на минимальное количество подпоследовательностей (не обязательно непрерывных), каждая из которых имеет лидера, и вывести это минимальное число. Можно доказать, что такое разбиение всегда возможно.
Входные данные
В первой строке входных данных находится одно целое число $n$ ($1 \le n \le 500\,000$), обозначающее длину последовательности.
Во второй строке входных данных находится последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).
Выходные данные
В единственной строке выходных данных должно находиться одно целое число, обозначающее минимально возможное количество подпоследовательностей, на которые можно разбить входную последовательность так, чтобы каждая результирующая подпоследовательность имела лидера.
Примеры
| Входные данные | Выходные данные |
|---|---|
5 1 2 3 1 2 |
2 |
Примечание
Входную последовательность можно разбить, например, на подпоследовательности $[1, 3, 1]$ и $[2, 2]$. Таким образом, обе результирующие подпоследовательности будут иметь лидера (соответственно числа $1$ и $2$).