Polish version    English version  
  History of OI -> XIII OI 2005/2006 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Regulations
For contestants
Helpful resources
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 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:
24



Print friendly version