Longest Repeated Substring

Time limit2sMemory limit128 MB

Summary

Find the length of the longest substring that occurs at least twice in a given string of up to 200,000 lowercase letters.

Level: Medium6 of 10
Topics: Binary search, String matching, Hash map, String
Solved: No attempts yet

Problem

You are given a string S of length L consisting only of lowercase English letters. A substring of S is called a repeated substring if it appears at least twice in the whole string.

Given S, find the length of the longest repeated substring.

Input

The first line contains the length L of the string. (1 ≤ L ≤ 200,000)

The second line contains the length-L string S, consisting only of lowercase English letters and written without spaces.

Output

Print the length of the longest repeated substring on the first line. If no repeated substring exists, print 0.

Examples2

Example 1
Input
```
28
tellmetellmetetetetetetellme
```
Expected output
```
11
```
Example 2
Input
```
5
jykim
```
Expected output
```
0
```