String Period Prediction

Consider a string S made only of lowercase English letters. Let S_i be the prefix of S consisting of the first i characters.

For S_i, choose the first p characters as one block. If the remaining i - p characters are exactly the same as the first i - p characters obtained by reading that block again from the beginning, then p is a predictable period length of S_i. The remaining part must not be longer than the block, so i - p <= p must hold.

Consider the following string.

a b a b a b a

It can be split into the first four characters a b a b and the remaining three characters a b a. The remaining three characters match the first three characters of the block, so length 4 is a predictable period length.

It can also be split into the first six characters a b a b a b and the remaining one character a. The remaining character again matches the first character of the block, so length 6 is also a predictable period length.

On the other hand, length 2, namely a b, is not a predictable period length for this string, because the remaining part has length 5, which is longer than the block of length 2.

For each S_i, let P_i be the largest predictable period length. If no length satisfies the conditions, P_i = 0. For the full string above, whose length is 7, the possible values are 4 and 6, so P_7 = 6.

Given a string S of length n, compute P_1 + P_2 + ... + P_n.

The first line contains the length n of the string S. (1 <= n <= 1,000,000)

The second line contains the lowercase string S with no spaces.

Print P_1 + P_2 + ... + P_n on the first line.

For S = babababa, the values are P_8 = 6, P_7 = 6, P_6 = 4, P_5 = 4, P_4 = 2, P_3 = 2, P_2 = 0, and P_1 = 0.