We call a sequence of strings t1, ..., tk a journey of length k, if for each i > 1 ti is a substring of ti - 1 and length of ti is strictly less than length of ti - 1. For example, {ab, b} is a journey, but {ab, c} and {a, a} are not.

Define a journey on string s as journey t1, ..., tk, such that all its parts can be nested inside s in such a way that there exists a sequence of strings u1, ..., uk + 1 (each of these strings can be empty) and s = u1 t1 u2 t2... uk tk uk + 1. As an example, {ab, b} is a journey on string abb, but not on bab because the journey strings ti should appear from the left to the right.

The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string s.

Input

The first line contains a single integer n (1 ≤ n ≤ 500 000) — the length of string s.

The second line contains the string s itself, consisting of n lowercase Latin letters.

Output

Print one number — the maximum possible length of string journey on s.

Examples

Input

7
abcdbcc


Output

3


Input

4
bbcb


Output

2

Note

In the first sample, the string journey of maximum length is {abcd, bc, c}.

In the second sample, one of the suitable journeys is {bb, b}.
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
char s[N];
int x[N], y[N], n;
int cnt[N], rk[N], SA[N];
int lg[N], st[N][20];
int cmp(int i, int j, int k) {
  return y[i] != y[j] ||
         (i + k > n ? -1 : y[i + k]) != (j + k > n ? -1 : y[j + k]);
}
void build_SA() {
  int m = 26;
  for (int i = (int)(1); i <= (int)(n); i++) cnt[x[i] = s[i] - 'a' + 1]++;
  for (int i = (int)(1); i <= (int)(m); i++) cnt[i] += cnt[i - 1];
  for (int i = (int)(n); i >= (int)(1); i--) SA[cnt[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int p = 0;
    for (int i = (int)(n - k + 1); i <= (int)(n); i++) y[++p] = i;
    for (int i = (int)(1); i <= (int)(n); i++)
      if (SA[i] > k) y[++p] = SA[i] - k;
    for (int i = (int)(1); i <= (int)(m); i++) cnt[i] = 0;
    for (int i = (int)(1); i <= (int)(n); i++) cnt[x[i]]++;
    for (int i = (int)(1); i <= (int)(m); i++) cnt[i] += cnt[i - 1];
    for (int i = (int)(n); i >= (int)(1); i--) SA[cnt[x[y[i]]]--] = y[i];
    swap(x, y);
    m = x[SA[1]] = 1;
    for (int i = (int)(2); i <= (int)(n); i++)
      x[SA[i]] = (m += cmp(SA[i], SA[i - 1], k));
  }
  for (int i = (int)(1); i <= (int)(n); i++) rk[SA[i]] = i;
  int p = 0;
  for (int i = (int)(1); i <= (int)(n); i++)
    if (rk[i] != 1) {
      p -= (p != 0);
      for (; s[i + p] == s[SA[rk[i] - 1] + p]; ++p)
        ;
      st[rk[i]][0] = p;
    }
  for (int i = (int)(2); i <= (int)(n); i++) lg[i] = lg[i / 2] + 1;
  for (int i = (int)(1); i <= (int)(18); i++)
    for (int j = (int)(1); j <= (int)(n - (1 << i) + 1); j++)
      st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
int nn, t[N * 4];
int f[N], ans;
void build_tr() {
  for (nn = 1; nn <= n + 1; nn <<= 1)
    ;
  for (int i = (int)(1); i <= (int)(2 * nn - 1); i++) t[i] = -(1 << 30);
}
void change(int x, int v) {
  x += nn;
  for (; x; x >>= 1) t[x] = max(t[x], v);
}
int ask(int l, int r) {
  int ans = -(1 << 30);
  l += nn - 1;
  r += nn + 1;
  for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (!(l & 1)) ans = max(ans, t[l ^ 1]);
    if (r & 1) ans = max(ans, t[r ^ 1]);
  }
  return ans;
}
bool check(int p, int func) {
  int pl = rk[p], pr = rk[p];
  for (int i = (int)(18); i >= (int)(0); i--) {
    if (pl > (1 << i) && st[pl - (1 << i) + 1][i] >= func - 1) pl -= (1 << i);
    if (pr + (1 << i) <= n && st[pr + 1][i] >= func - 1) pr += (1 << i);
  }
  if (ask(pl, pr) >= func - 1) return 1;
  pl = rk[p + 1];
  pr = rk[p + 1];
  for (int i = (int)(18); i >= (int)(0); i--) {
    if (pl > (1 << i) && st[pl - (1 << i) + 1][i] >= func - 1) pl -= (1 << i);
    if (pr + (1 << i) <= n && st[pr + 1][i] >= func - 1) pr += (1 << i);
  }
  if (ask(pl, pr) >= func - 1) return 1;
  return 0;
}
int main() {
  scanf("%d%s", &n, s + 1);
  build_SA();
  int func = 0;
  build_tr();
  for (int i = (int)(n); i >= (int)(1); i--) {
    func++;
    for (; func > 1 && !check(i, func); --func)
      if (i + func - 1 <= n) change(rk[i + func - 1], f[i + func - 1]);
    f[i] = func;
    ans = max(ans, f[i]);
  }
  printf("%d\n", ans);
}
