Balls
면접 대비시간 제한1초메모리 제한512 MB
일렬로 놓인 공들에서 연속 구간을 골라 과반수를 차지한 색이 아닌 공을 제거하는 과정을 반복할 때, 마지막에 남을 수 있는 색의 가짓수를 구한다.
문제
Zenyk placed n balls in a row on a table, and the i-th ball is colored in color ci. 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 ≤ 105) — the number of balls. The second line contains a list of n space-separated integers ci (1 ≤ ci ≤ 109) — 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.