Zenyk 在桌子上排成一排摆放了 $n$ 个球，第 $i$ 个球的颜色为 $c_i$。现在 Marichka 要玩这些球。
在每一轮中，她可以选择一段连续的球，该段球必须包含一种“主导颜色”。选择后，所有颜色与主导颜色不同的球都将被移除。
Marichka 希望进行若干轮操作（可以是零轮），使得最后剩下的所有球颜色相同。请找出最终可能剩下的不同颜色数量。
如果一段球中某种颜色的球数量超过总数的一半，则称该颜色为“主导颜色”。
第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示球的数量。第二行包含 $n$ 个空格分隔的整数 $c_i$ ($1 \le c_i \le 10^9$)，表示桌上球的初始颜色顺序。
仅输出一行，包含一个整数，即问题的答案。
7 3 1 3 2 1 2 3
2
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: