어색한 파티

Martin은 자신이 아는 모든 사람을 535번째 생일 파티에 초대했고, 전 세계에서 무려 n명이 초대를 수락했다.

자리 배치를 정할 때 Martin의 어머니 Margarethe는 모든 손님이 최대한 어색하게 앉도록 하기로 했다. 저녁 식사 중에 아무도 의미 있는 대화를 나누지 못하게 하고, 대신 모두가 조용히 맛있는 고수 수프를 즐기게 하려는 것이다. 속담에도 있듯이 "음식이 좋으면 대화는 죽는다"고 한다.

Margarethe는 손님이 긴 탁자 한 줄로 늘어앉아서 아무도 자기와 같은 언어를 쓰는 사람 옆에 앉지 않을 때 어색함이 최대가 된다는 것을 알고 있다. 나아가 그녀는 자리 배치의 어색함 정도를 같은 언어를 쓰는 두 손님 사이를 구분하는 좌석 수의 최솟값으로 정의했다. 같은 언어를 쓰는 두 사람이 없으면 어색함 정도는 n(손님 수)으로 정의한다. 서로 이웃한 두 좌석은 1만큼 떨어져 있다고 한다.

제안된 자리 배치에서 쓰이는 언어가 주어질 때, Margarethe가 어색함 정도를 구하도록 도와줄 수 있는가?

첫째 줄에는 손님 수를 나타내는 정수 n(1 ≤ n ≤ 100 000)이 주어진다. 둘째 줄에는 n개의 정수가 주어지며, i번째 정수 xi(0 ≤ xi ≤ 109)는 제안된 배치에서 i번째 자리에 앉은 손님이 쓰는 언어를 나타낸다. 각 손님은 정확히 하나의 언어를 쓴다.

제안된 자리 배치의 어색함 정도를 나타내는 정수 하나를 출력한다.