마스코트 정하기

$N$명의 학생들이 건국대학교의 마스코트를 투표하기 위해 모였다!

투표를 하려는 건국대학교의 학생들은 한 줄로 나란히 서 있다. 사람들은 서 있는 순서대로 $1$번, $2$번, $\cdots$, $N$번 학생이라고 한다.

각 학생은 $1$과 $N$ 사이의 정수 번호의 마스코트 후보에게 투표하려 하고 있다. $i$번째 학생은 $A_i$번에 투표한다.

유력 마스코트 후보인 쿠는 자신이 마스코트가 되기 위해 투표를 하려는 학생들을 쫓아내려고 했다!

당신은 아래의 행동을 원하는 만큼 반복할 수 있다.

• $1 \le L \le R \le N$인 두 정수 $L,\ R$을 골라 $L$번, $L + 1$번, , 번, 번 사람 중 투표장에 남아 있는 학생들을 모두 투표장에서 내쫓는다. 단, 모든 학생을 투표장에서 내쫓을 수는 없다. 투표장에서 내쫓아진 학생들은 투표에 참가할 수 없으며, 따라서 투표한 학생의 수에 포함되지 않는다.

투표한 학생이 $m$명일 때, $\lceil\frac{m}{2}\rceil$명 이상의 표를 받은 후보가 마스코트가 된다. (단, 두 후보가 동시에 마스코트가 될 수 있다.)

$1$번 마스코트 후보인 쿠가 마스코트가 되기 위해, 당신은 최소 몇 번의 행동을 해야 하는지 구해보자.

첫째 줄에 투표를 하려는 학생의 수 $N$이 주어진다. $(1 \le N \le 200\ 000)$

둘째 줄에 각 학생이 투표하려는 번호를 나타내는 $N$개의 정수 $A_1,A_2,\cdots$이 주어진다.

$1$번 마스코트 후보인 쿠가 마스코트가 되기 위한 최소 행동 횟수를 출력한다.