History of OI -> XIII OI 2005/2006 -> Problems

News

Links

SIO

MAIN

Task: Periods of Words

Available memory: 32 MB

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A = BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string A, if there is a string B, that A = PB. In other words, prefixes of A are the initial fragments of A. In addition, if P $$ \neq$% WIDTH=16 HEIGHT=30$ A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of A, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task

Write a programme that:

reads from the standard input the string's length and the string itself,
calculates the sum of lengths of maximum periods of all its prefixes,
writes the result to the standard output.

Input

In the first line of the standard input there is one integer k ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ k $$ \le$% WIDTH=16 HEIGHT=30$ 1 000 000) -- the length of the string. In the following line a sequence of exactly k lower-case letters of the English alphabet is written -- the string.

Output

In the first and only line of the standard output your programme should write an integer -- the sum of lengths of maximum periods of all prefixes of the string given in the input.

Example

For the following input data:

8
babababa

the correct answer is:

Print friendly version