Строка \textbf{P} называется \textit{префиксом} строки \textbf{A}, если \textbf{A=PB}, где \textbf{P} или \textbf{B} могут быть пустыми строками. Строка \textbf{P }является \textit{нетривиальным префиксом} строки \textbf{A}, если \textbf{A=PB}, и при этом ни \textbf{P}, ни \textbf{B} не пустые. Строка \textbf{Q} называется \textit{периодом строки} \textbf{A}, если \textbf{Q} -- нетривиальный префикс \textbf{A} и при этом \textbf{A} -- префикс (но не обязательно нетривиальный) строки \textbf{QQ}. К примеру, строки \textbf{abab} и \textbf{ababab} являются периодами строки \textbf{abababa}. Максимальный период строки \textbf{A} -- самый длинный из ее периодов, либо пустая строка, если у \textbf{A} нет ни одного периода. К примеру, максимальный период строки \textbf{ababab} -- \textbf{abab}, максимальный период строки \textbf{abc} -- пустая строка. Напишите программу, которая найдет сумму длин максимальных периодов для всех префиксов заданной строки \textbf{A}. \InputFile В первой строке входного файла содержится одно целое число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{1000000}) -- длина строки \textbf{A}. Во второй строке содержится последовательность из \textbf{k} маленьких букв английского алфавита -- строка \textbf{A}. \OutputFile В единственной строке выходного файла выведите целое число -- сумму длин максимальных периодов каждого префикса строки \textbf{A}.