공

Zenyk은 탁자 위에 n개의 공을 한 줄로 놓았고, i번째 공은 색 ci로 칠해져 있다. 이제 Marichka가 Zenyk의 공을 가지고 놀려고 한다.

한 번의 턴에서 그녀는 과반수 색을 가진 연속한 공들의 구간을 고를 수 있다. 그 뒤 선택한 공들 중 과반수 색이 아닌 공들은 모두 제거된다.

Marichka는 몇 번의 턴을 거친 뒤(0번일 수도 있다) 남은 모든 공의 색이 같게 만들고자 한다. 마지막에 남을 수 있는 서로 다른 색의 개수를 구하여라.

선택한 공들 중 절반보다 많은 수가 그 색으로 칠해져 있으면 그 색을 과반수 색이라고 한다.

첫째 줄에는 정수 n (1 ≤ n ≤ 105)이 주어지며, 이는 공의 개수이다. 둘째 줄에는 n개의 정수 ci (1 ≤ ci ≤ 109)가 공백으로 구분되어 주어지며, 이는 탁자에 놓인 순서대로의 공의 초기 색이다.

한 줄에 정수 하나를 출력한다. 이는 문제의 답이다.