시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 246 61 43 24.157%

문제

알파벳 소문자들로만 이루어진 문자열을 생각하자. 이런 문자열을 읽어 나가다 보면, 문자열의 주기가 예측되는 순간이 있다. 다음과 같은 문자열을 예로 들어 보자.

a b a b a b a

이 문자열을 네 번째 문자까지의 문자열 'a b a b'와, 그 뒤에 남은 'a b a'로 나누어 생각해 볼 수 있다. 이렇게 하면 뒤쪽 문자열은 앞쪽 네 개의 문자 중 세 번째 문자까지가 반복되다가 끝나는 꼴이다.

a b a b a b a

또한, 여섯 번째 문자까지의 문자열 'a b a b a b'와, 그 뒤에 남은 'a'로 나누어서 생각할 수도 있다. 이 경우에도 뒤쪽 문자열은 앞쪽 문자열이 반복되다가 끝나는 꼴이다.

즉, 예시된 문자열은 'a b a b'혹은, 'a b a b a b'가 반복되는 문자열의 일부라고 예상할 수 있는 것이다. 단, 이러한 추정에서 뒤쪽 문자열이 앞쪽 문자열보다 길면 안 된다. 예를 들어 'a b'는 이 문자열의 주기로 예측하기에는 너무 짧다.

이제는 어떤 문자열 S에 대해, 첫 번째 문자부터, i번째 문자까지로 이루어진 부분 문자열 Si를 생각해 보자. 모든  각각에 대해, 위에 예시된 것처럼 문자열의 주기를 추정할 수 있다. 우리가 관심 있는 것은 이렇게  각각에 Si대해 추정할 수 있는 주기 중 가장 긴 것의 길이이다. 이를 Pi라고 하자. 예시된 문자열에서 P7은 4와 6 중 최대값인 6이 된다.

길이가 n인 문자열 S가 주어졌을 때, P1+P2+...+Pn을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S의 길이 n이 주어진다. (1<=n<=1,000,000) 둘째 줄에 문자열 S가 공백 없이 주어진다.

출력

첫째 줄에, P1+P2+...+Pn의 값을 출력한다.

예제 입력

8
babababa

예제 출력

24

힌트

P8 = 6, P7 = 6, P6 = 4, P5 = 4, P4 = 2, P3 = 2, P2 = 0, P1 = 0