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
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    char[] s = scanner.next().toCharArray();
    long[] M = {999_999_937, 1_000_000_007};
    long B = 9973;
    int left = 0;
    int right = N / 2 + 1;
    while (right - left > 1) {
      int mid = (left + right) / 2;
      if (possible(s, mid, N, B, M)) left = mid;
      else right = mid;
    }
    System.out.println(left);
  }

  private static boolean possible(char[] s, int K, int N, long B, long[] M) {
    long[] bn = new long[M.length];
    for (int i = 0; i < M.length; i++) {
      bn[i] = 1;
      for (int j = 0; j < K - 1; j++) {
        bn[i] *= B;
        bn[i] %= M[i];
      }
    }

    HashMap<Tuple, Integer> occurrences = new HashMap<>();
    long[] hash = new long[M.length];
    for (int i = 0; i < M.length; i++) {
      hash[i] = hash(s, K, B, M[i]);
    }
    occurrences.put(new Tuple(hash), 0);
    for (int i = 1; i <= N - K; i++) {
      for (int j = 0; j < M.length; j++) {
        hash[j] -= s[i - 1] * bn[j] % M[j];
        if (hash[j] < 0) hash[j] += M[j];
        hash[j] *= B;
        hash[j] %= M[j];
        hash[j] += s[i + K - 1];
        if (hash[j] >= M[j]) hash[j] -= M[j];
      }
      Tuple key = new Tuple(hash);
      if (occurrences.containsKey(key)) {
        if (occurrences.get(key) + K <= i) return true;
      }
      else occurrences.put(key, i);
    }
    return false;
  }

  private static long hash(char[] s, int len, long B, long M) {
    if (s.length < len) throw new IllegalArgumentException("len must be equal to or more than s.length: len=" + len + ", s.length=" + s.length);
    long hash = 0;
    for (int i = 0; i < len; i++) {
      hash *= B;
      hash %= M;
      hash += s[i];
      if (hash >= M) hash -= M;
    }
    return hash;
  }

  private static class Tuple {
    private final long[] elements;

    private Tuple(long[] elements) {
      this.elements = Arrays.copyOf(elements, elements.length);
    }

    @Override public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Tuple tuple = (Tuple) o;
      return Arrays.equals(elements, tuple.elements);
    }

    @Override public int hashCode() {
      return Arrays.hashCode(elements);
    }
  }
}
