PWN 사전에 따르면 "리더(lider)"는 "정당, 노동조합 또는 기타 사회 단체의 지도자" 등을 의미합니다. 반면 알고리즘 분야에서 수열의 리더란, 수열 내에서 등장 횟수가 수열 전체 길이의 절반을 엄격하게 초과하는 요소를 말합니다. 예를 들어, 수열 $[7, 2, 5, 7, 7]$의 리더는 $7$이며, 수열 $[2, 3, 2, 3]$은 리더가 존재하지 않습니다.

이 문제에서는 후자의 의미를 다룹니다. 주어진 수열을 리더를 가진 최소 개수의 수열들(연속적일 필요는 없음)로 분할하고, 그 최소 개수를 출력하는 프로그램을 작성하세요. 이러한 분할은 항상 가능함이 증명되어 있습니다.

입력

첫 번째 줄에는 수열의 길이를 나타내는 정수 $n$ ($1 \le n \le 500\,000$)이 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)으로 이루어진 수열이 주어집니다.

출력

입력받은 수열을 각 수열이 리더를 가지도록 분할할 때, 가능한 최소 수열의 개수를 한 줄에 출력하세요.

예제

입력 1

5
1 2 3 1 2

출력 1

2

참고

예제 설명: 입력 수열을 예를 들어 $[1, 3, 1]$과 $[2, 2]$로 나눌 수 있습니다. 이렇게 하면 두 결과 수열 모두 리더를 가지게 됩니다(각각 $1$과 $2$).