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 = 500010, TOP = 20;
int f[N];
char s[N];
int ans, n;
namespace Sa {
int a[N], b[N], c[N], sa[N], rk[N], height[N];
int mn[N][TOP + 1];
int mx;
bool cmp(int x, int y, int len, int *r) {
  return r[x] == r[y] && r[x + len] == r[y + len];
}
void sort(int n) {
  for (int i = 0; i <= mx; ++i) c[i] = 0;
  for (int i = 1; i <= n; ++i) c[a[b[i]]]++;
  for (int i = 1; i <= mx; ++i) c[i] += c[i - 1];
  for (int i = n; i >= 1; --i) sa[c[a[b[i]]]--] = b[i];
}
void get_sa(int n) {
  mx = 0;
  for (int i = 1; i <= n; ++i)
    a[i] = s[i] - 'a' + 1, mx = max(a[i], mx), b[i] = i;
  sort(n);
  int cnt = 0;
  for (int len = 1; cnt < n; len <<= 1) {
    cnt = 0;
    for (int i = n - len + 1; i <= n; ++i) b[++cnt] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) b[++cnt] = sa[i] - len;
    sort(n);
    swap(a, b);
    a[sa[1]] = 1;
    cnt = 1;
    for (int i = 2; i <= n; a[sa[i]] = cnt, ++i)
      if (!cmp(sa[i], sa[i - 1], len, b)) ++cnt;
    mx = cnt;
  }
}
void calc(int n) {
  for (int i = 1; i <= n; ++i) mn[i][0] = height[i];
  for (int j = 1; j <= TOP; ++j)
    for (int i = n - (1 << j) + 1; i >= 1; --i)
      mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
}
int lcp(int x, int y) {
  if (x == y) return n - sa[x] + 1;
  if (x > y) swap(x, y);
  ++x;
  int len = y - x + 1, lg = (int)(log(1.0 * len) / log(2.0));
  return min(mn[x][lg], mn[y - (1 << lg) + 1][lg]);
}
void get_height(int n) {
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  int k = 0;
  for (int i = 1; i <= n; ++i) {
    if (k > 0) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    height[rk[i]] = k;
  }
  calc(n);
}
}  // namespace Sa
namespace Seg {
const int N = ::N * 4;
int ch[N][2], mx[N];
int n, tot;
void pushup(int x) { mx[x] = max(mx[ch[x][0]], mx[ch[x][1]]); }
void _build(int x, int l, int r) {
  mx[x] = -1;
  if (l == r) return;
  int mid = l + r >> 1;
  ch[x][0] = ++tot;
  _build(ch[x][0], l, mid);
  ch[x][1] = ++tot;
  _build(ch[x][1], mid + 1, r);
  pushup(x);
}
void build(int _n) {
  n = _n;
  tot = 1;
  _build(1, 1, n);
}
void _insert(int x, int d, int lx, int rx, int delta) {
  if (lx == rx) {
    mx[x] = delta;
    return;
  }
  int mid = lx + rx >> 1;
  if (d <= mid)
    _insert(ch[x][0], d, lx, mid, delta);
  else
    _insert(ch[x][1], d, mid + 1, rx, delta);
  pushup(x);
}
void insert(int d, int delta) {
  if (d) _insert(1, d, 1, n, delta);
}
int _query(int x, int l, int r, int lx, int rx) {
  if (l <= lx && rx <= r) return mx[x];
  int mid = lx + rx >> 1;
  if (r <= mid)
    return _query(ch[x][0], l, r, lx, mid);
  else if (l > mid)
    return _query(ch[x][1], l, r, mid + 1, rx);
  else
    return max(_query(ch[x][0], l, mid, lx, mid),
               _query(ch[x][1], mid + 1, r, mid + 1, rx));
}
int query(int l, int r) { return (l > 0 && r > 0) ? _query(1, l, r, 1, n) : 0; }
}  // namespace Seg
int get_mx(int rk, int dw) {
  if (dw == 0) return Seg::mx[1];
  int L = rk, R = rk, l = 1, r = rk - 1, mid;
  while (l <= r) {
    mid = l + r >> 1;
    if (Sa::lcp(mid, rk) >= dw)
      L = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  l = rk + 1;
  r = n;
  while (l <= r) {
    mid = l + r >> 1;
    if (Sa::lcp(mid, rk) >= dw)
      R = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return Seg::query(L, R);
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  Sa::get_sa(n);
  Sa::get_height(n);
  f[n] = 1;
  ans = 1;
  Seg::build(n);
  for (int i = n - 1; i >= 1; --i) {
    for (int k = f[i + 1] + 1;; --k) {
      Seg::insert(Sa::rk[i + k], f[i + k]);
      if (max(get_mx(Sa::rk[i], k - 1), get_mx(Sa::rk[i + 1], k - 1)) >=
          k - 1) {
        f[i] = k;
        break;
      }
    }
    ans = max(ans, f[i]);
  }
  printf("%d\n", ans);
}
