준원이는 색깔이 다양한 공 N개를 한 줄에 놓고 게임을 하려합니다. 가장 왼쪽에 있는 공부터 1번이라고 놓았을 때 ~i (1\le i\le N)~번째 공은 색깔이 C_i입니다.

게임은 다음과 같이 진행됩니다.

• 현재 상태에서 연속한 공들을 선택합니다.
• 만약 어떤 색깔이 선택된 공들의 절반보다 많다면 그 색깔을 제외한 나머지 공들을 제거한 후 남은 공은 제자리에 놓습니다. 그렇지 않다면 모든 공을 다시 제자리에 놓습니다.

준원이는 색깔이 단 하나만 남을 때까지 게임을 반복합니다. 준원이가 게임을 마쳤을 때 남을 수 있는 색깔의 개수를 구하세요.

입력

첫째 줄에 공의 개수 N이 주어집니다. (1 \le N \le 10\ 000)

둘째 줄에 1번 공부터 각 공의 색깔이 주어집니다. (1 \le C_i \le 5\ 000)

출력

게임이 끝나고 남을 수 있는 색깔의 개수를 출력합니다.

입력 예제 1

7
3 1 3 2 1 2 3

출력 예제 1

2

2하고 3이 가능한 색깔입니다.