Періоди слів
Рядок P називається префіксом рядка A, якщо A=PB, де P або B можуть бути порожніми рядками. Рядок P є нетривіальним префіксом рядка A, якщо A=PB, і при цьому ні P, ні B не порожні. Рядок Q називається періодом рядка A, якщо Q – нетривіальний префікс A і при цьому A – префікс (але не обов'язково нетривіальний) рядка QQ. Наприклад, рядки abab та ababab є періодами рядка abababa.
Максимальний період рядка A – самий довгий з його періодів, або порожній рядок, якщо у A немає жодного періода. Наприклад, максимальний період рядки ababab – abab, максимальний період рядка abc – порожній рядок.
Напишіть програму, яка знайде суму довжин максимальних періодів для усіх префіксів заданого рядка A.
Вхідні дані
У першому рядку вхідного файлу міститься одне ціле число k (1 ≤ k ≤ 1000000) – довжина рядка A. У другому рядку міститься послідовність з k маленьких букв англійського алфавіту – рядок A.
Вихідні дані
У єдиному рядку вихідного файлу виведіть ціле число – суму довжин максимальних періодів кожного префікса рядка A.