Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

* l_1 + len \leq l_2

* S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)




If there is no such integer len, print 0.

Constraints

* 2 \leq N \leq 5 \times 10^3
* |S| = N
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Examples

Input

5
ababa


Output

2


Input

2
xy


Output

0


Input

13
strangeorange


Output

5
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

MOD = 10**9 + 7
P = 97
def solve(N, S):
    A = [0]
    rawA = []
    #powers = []
    ha = 0
    #pwr = 1
    for c in S:
        x = ord(c) - ord('a') + 2
        rawA.append(x)
        #ha += x * pwr
        #ha %= MOD
        #powers.append(pwr)
        ha += x
        A.append(ha)
        #pwr *= P
        #pwr %= MOD
    #powers.append(pwr)

    def gethash(i, j):
        ha = A[j] - A[i]
        #ha *= pow(powers[i-1], MOD-2, MOD)
        ha %= MOD
        #print 'gh', i,j, ';', ha
        return ha

    # A
    #print 'g1',gethash(2, 2+5)
    #print 'g2', gethash(8, 8+5)
    
    def doublematch(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            for j in xrange(i + L, N - L + 1):
                if gethash(i, i+L) == gethash(j, j+L) and rawA[i:i+L] == rawA[j:j+L]:
                    return True

    #print map(doublematch, range(len(A)))
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if doublematch(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(rri(), rr())
