시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB198758.333%

문제

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.

예제 입력 1

7
3 1 3 2 1 2 3

예제 출력 1

2

출처

Camp > Petrozavodsk Programming Camp > Winter 2020 > Day 6: Lviv NU Contest F번

  • 데이터를 추가한 사람: shiftpsh