18735번 - Balls 다국어

Zenyk placed n balls in a row on a table, and the i-th ball is colored in color c_i. Now Marichka is going to play with Zenyk’s balls.

In a single turn, she can pick a sequence of consecutive balls which has a dominant color. After that, all selected balls that are colored in a different color than the dominant will be removed.

Marichka wants to make some number of turns (possibly zero) after which all remaining balls will be colored in the same color. Find out how many different colors could be left at the end.

Color is considered dominant if more than half of the selected balls are colored in it.

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of balls. The second line contains a list of n space-separated integers c_i (1 ≤ c_i ≤ 10⁹) — the initial colors of the balls in the order they are placed on the table.

In the only line print a single integer — the answer to the problem.