ABB

Fernando는 University of Waterloo에서 얼마 전 시작한 개발 프로젝트를 마무리하도록 고용되었다. 대학 측은 캠퍼스 밖에 중요한 외국 방문객과 협력자를 위한 대표 방갈로 거리를 만들고자 했다.

현재 이 거리는 일부분만 지어져 있으며, 호숫가에서 시작해 숲 속까지 이어지다가 그곳에서 끝난다. Fernando의 임무는 숲 쪽 끝에서 방갈로를 더 지어 거리를 완성하는 것이다. 기존 방갈로는 모두 거리의 한쪽 편에 서 있고, 새 방갈로도 같은 편에 지어야 한다. 방갈로는 종류도 다양하고 색칠된 색도 다양하다.

Fernando에게 거리의 전체 배치는 다소 혼란스러워 보인다. 자신이 설계한 새 방갈로를 추가하면 더 혼란스러워질까 봐 걱정된다. 온갖 방갈로 모양이 만드는 혼란을 상쇄하기 위해, 그는 새 방갈로의 색을 적절히 골라 배치에 질서를 더하고자 한다. 프로젝트가 끝나면 방갈로 색의 전체 수열은 대칭이 된다. 즉, 거리의 어느 쪽 끝에서 보아도 색 수열이 같다.

Fernando는 여러 가지 궁금증 중에서도, 스스로 정한 방갈로 색 제약을 지키면서 프로젝트를 완성하려면 색을 알맞게 칠한 새 방갈로를 최소 몇 개 지어야 하는지 알고 싶어 한다.

첫째 줄에 거리에 있는 기존 방갈로의 수를 나타내는 정수 N (1 ≤ N ≤ 4 · 105)이 주어진다. 다음 줄에는 호숫가에서 시작하는 쪽부터 기존 방갈로의 색 수열이 주어진다. 이 줄은 N개의 소문자("a"부터 "z"까지)로 이루어진 문자열 하나이며, 서로 다른 문자는 서로 다른 색을 나타낸다.

Fernando가 요구하는 색 대칭을 만족하도록 거리의 숲 쪽 끝에 추가하고 알맞게 칠해야 하는 방갈로의 최소 개수를 출력한다.