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;
const int S = 1000005;
int n;
char s[N];
struct vert {
  int son[26], f[20], ln;
} tr[S];
int lst = 1, cnt = 1;
inline void ins(int x) {
  int p = lst, np = lst = ++cnt;
  tr[np].ln = tr[p].ln + 1;
  while (p && !tr[p].son[x]) tr[p].son[x] = np, p = tr[p].f[0];
  if (!p)
    tr[np].f[0] = 1;
  else {
    int q = tr[p].son[x];
    if (tr[q].ln == tr[p].ln + 1)
      tr[np].f[0] = q;
    else {
      int nq = ++cnt;
      tr[nq] = tr[q];
      tr[nq].ln = tr[p].ln + 1;
      tr[np].f[0] = tr[q].f[0] = nq;
      while (p && tr[p].son[x] == q) tr[p].son[x] = nq, p = tr[p].f[0];
    }
  }
}
int pos[N];
char tmp[N];
int tp = 0;
int T = 0;
inline void ddfs(int u) {
  cout << ++T << ' ' << u << ' ';
  for (int i = 1; i <= tp; i++) cout << tmp[i];
  cout << endl;
  for (int i = 0; i < 26; i++) {
    if (tr[u].son[i]) {
      tmp[++tp] = 'a' + i;
      ddfs(tr[u].son[i]);
      tp--;
    }
  }
}
const int E = 1000005;
int to[E], nx[E], h[S], tot = 0;
inline void add(int a, int b) {
  to[++tot] = b;
  nx[tot] = h[a];
  h[a] = tot;
}
int dfn[S], dc = 0, siz[S];
inline void dfs(int u) {
  dfn[u] = ++dc;
  siz[u] = 1;
  for (int i = h[u]; i; i = nx[i]) {
    dfs(to[i]);
    siz[u] += siz[to[i]];
  }
}
int v[S << 2];
inline void up(int x) { v[x] = max(v[x << 1], v[x << 1 | 1]); }
inline void build(int x, int l, int r) {
  if (l == r) {
    v[x] = 0;
    return;
  }
  build(x << 1, l, ((l + r) >> 1));
  build(x << 1 | 1, ((l + r) >> 1) + 1, r);
  up(x);
}
inline void upd(int x, int l, int r, int p, int val) {
  if (l == r) {
    v[x] = val;
    return;
  }
  if (((l + r) >> 1) >= p)
    upd(x << 1, l, ((l + r) >> 1), p, val);
  else
    upd(x << 1 | 1, ((l + r) >> 1) + 1, r, p, val);
  up(x);
}
inline int query(int x, int l, int r, int nl, int nr) {
  if (nl <= l && r <= nr) return v[x];
  int res = 0;
  if (((l + r) >> 1) >= nl)
    res = max(res, query(x << 1, l, ((l + r) >> 1), nl, nr));
  if (((l + r) >> 1) < nr)
    res = max(res, query(x << 1 | 1, ((l + r) >> 1) + 1, r, nl, nr));
  return res;
}
inline void epp() {
  for (int i = 2; i <= cnt; i++) add(tr[i].f[0], i);
}
inline void fpp(int u) {
  for (int i = 1; i <= 19; i++) tr[u].f[i] = tr[tr[u].f[i - 1]].f[i - 1];
  for (int i = h[u]; i; i = nx[i]) fpp(to[i]);
}
inline void pp() {
  epp();
  fpp(1);
  dfs(1);
  build(1, 1, cnt);
}
int f[N];
int ans = 0;
inline int get(int p, int len) {
  for (int i = 19; i >= 0; i--) {
    if (tr[p].f[i] && tr[tr[p].f[i]].ln >= len) {
      p = tr[p].f[i];
    }
  }
  return p;
}
inline bool check1(int p, int x) {
  if (p - 1 < 1) return 0;
  p = pos[p - 1];
  p = get(p, x - 1);
  int tmp = query(1, 1, cnt, dfn[p], dfn[p] + siz[p] - 1);
  return tmp >= x - 1;
}
inline bool check2(int p, int x) {
  p = pos[p];
  p = get(p, x - 1);
  int tmp = query(1, 1, cnt, dfn[p], dfn[p] + siz[p] - 1);
  return tmp >= x - 1;
}
inline bool check(int p, int x) { return check1(p, x) || check2(p, x); }
inline int read() {
  int f = 0, s = 0;
  char c = getchar();
  while (c > '9' || c < '0') f = (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    s = (s << 3) + (s << 1) + (c ^ '0'), c = getchar();
  return f ? -s : s;
}
int main() {
  n = read();
  scanf("%s", s + 1);
  reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; i++) {
    ins(s[i] - 'a');
    pos[i] = lst;
  }
  f[0] = 0;
  pp();
  for (int i = 1, p = 0; i <= n; i++) {
    f[i] = f[i - 1] + 1;
    while (!check(i, i - p)) {
      p++;
      f[i] = i - p;
      upd(1, 1, cnt, dfn[pos[p]], f[p]);
    }
    ans = max(ans, f[i]);
  }
  printf("%d", ans);
  return 0;
}
