Background

PA 2024 1B

Problem Description

This problem is translated from PA 2024 Round 1 Liderzy.

According to the PWN dictionary (a Polish dictionary), “lider” means “a leader of a political party, a trade union, or another social organization”. On the other hand, in algorithms, an element that appears strictly more than half of the sequence length is called the leader element of the sequence. For example, the leader element of the sequence $[7, 2, 5, 7, 7]$ is the number $7$, while the sequence $[2, 3, 2, 3]$ has no leader element.

In this problem, we focus on the second meaning of the word “lider”. Given a sequence, your task is to split it into the minimum number of sequences (not necessarily contiguous) such that each sequence has a leader element, and output this minimum number. It can be proven that such a partition is always possible.

Input Format

The first line contains an integer $n\ (1\le n\le 5\times 10^5)$, the length of the sequence.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n\ (1\le a_i\le n)$, representing the sequence.

Output Format

Output one integer on one line, the answer.

5
1 2 3 1 2

2

Hint

The input sequence can be partitioned into $[1, 3, 1]$ and $[2, 2]$. Then both resulting sequences have a leader element (respectively $1$ and $2$).

Translated by ChatGPT 5