2168. Runes in the Field @ Timus Online Judge

2168. Runes in the Field

Time limit: 2.0 second
Memory limit: 256 MB

Vadim decided to take a walk in the field again. There he saw N runes with different engravings in the form of lowercase Latin letters, lying in a row. Each of them is very expensive, so Vadim decided to collect as many as possible.

After futile attempts to lift the first rune, he went around all of them and found an ancient manuscript on the ground. It said that it is possible to lift any number of runes at once under several conditions:

All such runes must be lying in order, that is, assuming that the runes are numbered from 1 to N, it is possible to lift the runes from the l-th to the r-th, and all these runes must not have been lifted yet;
Some non-trivial prefix of this range of runes must coincide with the suffix of this range of the same length. Non-trivial means not coinciding with the entire range. For example, Vadim will be able to lift the range “abcdab”, because there is a prefix “ab”, he will be able to lift “aa”, because there is a prefix “a”, he will also be able to lift “abcabcab”, because there is a prefix “abcab”, but he will not be able to lift “abc” or “a” in any way;
These actions can be repeated any number of times, but it is not allowed to return the runes back or to another place.

After reading this manuscript, Vadim realized that he has no time to think at all, so he asked you to help him calculate the maximum number of runes he can take with him.

Input

The first line contains an integer N — the number of runes in the field (1 ≤ N ≤ 10⁵).

The second line describes these runes in a single line, consisting of lowercase Latin letters.

Output

Print a single integer — the maximum number of runes that can be lifted from the field using a sequence of actions.

Samples

input	output
6 abcdab	6
7 abcdabd	6
6 abacdc	6

Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2022