문자열 주기 예측

알파벳 소문자로만 이루어진 문자열 S를 생각하자. 접두사 S_i를 S의 첫 번째 문자부터 i번째 문자까지로 이루어진 문자열이라고 하자.

S_i에서 길이 p인 앞부분을 하나의 블록으로 잡았을 때, 남은 i - p개의 문자가 그 블록을 처음부터 다시 읽은 앞부분과 정확히 같으면 p를 S_i의 예측 가능한 주기 길이라고 한다. 이때 남은 부분이 블록보다 길면 안 되므로 i - p <= p이어야 한다.

다음 문자열을 살펴보자.

a b a b a b a

이 문자열은 앞의 네 문자 a b a b와 뒤의 세 문자 a b a로 나눌 수 있다. 뒤의 세 문자는 앞의 네 문자 블록을 처음부터 다시 읽은 세 문자와 같으므로, 길이 4는 예측 가능한 주기 길이이다.

또한 앞의 여섯 문자 a b a b a b와 뒤의 한 문자 a로 나눌 수도 있다. 이 경우에도 뒤의 한 문자는 앞 블록을 처음부터 다시 읽은 첫 문자와 같으므로, 길이 6도 예측 가능한 주기 길이이다.

반대로 길이 2인 a b는 이 문자열의 예측 가능한 주기 길이가 아니다. 남은 부분의 길이 5가 앞 블록의 길이 2보다 길기 때문이다.

각 S_i에 대해 예측 가능한 주기 길이 중 가장 큰 값을 P_i라고 하자. 조건을 만족하는 길이가 없다면 P_i = 0이다. 위 문자열 전체의 길이가 7일 때는 가능한 값 4와 6 중 최댓값이 6이므로 P_7 = 6이다.

길이가 n인 문자열 S가 주어졌을 때, P_1 + P_2 + ... + P_n을 구하시오.

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

둘째 줄에 알파벳 소문자로만 이루어진 문자열 S가 공백 없이 주어진다.

첫째 줄에 P_1 + P_2 + ... + P_n의 값을 출력한다.

S = babababa인 경우 P_8 = 6, P_7 = 6, P_6 = 4, P_5 = 4, P_4 = 2, P_3 = 2, P_2 = 0, P_1 = 0이다.