차고

다양한 색이 칠해진 자동차들이 일렬로 줄을 지어 차례대로 차고로 들어간다.

차고는 여러 행으로 구성되어 있으며, 각 행은 모든 자동차가 들어갈 수 있을 만큼 충분히 길다. 행의 개수 또한 자동차의 개수보다 많다.

자동차가 차고의 어떤 행에 들어갈 때, 같은 색을 가진 자동차는 모두 같은 행에 주차되어야 하며, 같은 색의 자동차 사이엔 다른 색의 자동차가 있을 수 없다. 즉, 한 색의 자동차는 한 행에 모두 인접하게 주차되어야 한다. 하지만, 한 행에 여러 색의 자동차들이 주차될 수는 있다.

아래 그림은 $10$대의 자동차가 들어온 순서에 따라 어느 차고에 주차되었는지를 보여준다. 이 그림에서 알파벳 대문자는 각 자동차들을 의미한다. 괄호 내에 있는 수는 각 자동차들의 색을 의미한다. 이때 같은 색을 가진 자동차는 모두 같은 행에 주차되어 있으며, 세 번째 행과 같이 한 행에 여러 색의 자동차들이 주차될 수 있다. 총 $3$개의 행을 이용해서 위의 조건들을 만족하며 자동차를 모두 주차할 수 있음을 알 수 있다.

자동차들의 색이 차고로 들어가는 순서대로 주어질 때, 위 조건들을 만족하며 모든 자동차를 주차하기 위해 사용해야 하는 행의 최소 개수를 구하여라. 단, 자동차가 한 대라도 주차된 행만 사용된 것으로 본다.

입력 형식

첫 번재 줄에는 주차해야 할 자동차의 개수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

두 번째 줄에는 $N$개의 자연수가 주어지는데, 각각 자동차의 색을 나타내고, 이 값은 최소 $1$ 최대 $1\,000\,000\,000$ 이다. (위의 그림에서 자동차를 구별하기 위해 사용되었던 알파벳은 주어지지 않는다.)

출력 형식

주어진 입력에 대해, 위 조건들을 만족하며 모든 자동차를 주차하기 위해 사용해야 하는 행의 최소 개수를 출력하여라.

예제 1

10
1 5 7 1 7 7 3 1 5 3

3

예제 2

8
2 2 3 3 4 4 2 2

2

예제 3

12
1 2 3 1 2 3 6 7 8 6 7 8

3

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설