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>
const int N = 1000000;
int ch[26][N + 5], fa[N + 5], len[N + 5], ncnt, lst, rt;
void extend(int c) {
  int cur = (++ncnt), p = lst;
  len[cur] = len[lst] + 1, lst = cur;
  while (p && !ch[c][p]) ch[c][p] = cur, p = fa[p];
  if (!p)
    fa[cur] = rt;
  else {
    int q = ch[c][p];
    if (len[p] + 1 == len[q])
      fa[cur] = q;
    else {
      int nq = (++ncnt);
      fa[nq] = fa[q], len[nq] = len[p] + 1;
      for (int i = 0; i < 26; i++) ch[i][nq] = ch[i][q];
      fa[q] = fa[cur] = nq;
      while (p && ch[c][p] == q) ch[c][p] = nq, p = fa[p];
    }
  }
}
struct node {
  int x, l;
};
node nxt(const node &k, int c) { return (node){ch[c][k.x], k.l + 1}; }
node fat(const node &k) {
  if (k.l - 1 == len[fa[k.x]])
    return (node){fa[k.x], k.l - 1};
  else
    return (node){k.x, k.l - 1};
}
std::vector<int> v[N + 5];
int dl[N + 5], dr[N + 5], dcnt;
void dfs(int x) {
  dl[x] = (++dcnt);
  for (unsigned i = 0; i < v[x].size(); i++) dfs(v[x][i]);
  dr[x] = dcnt;
}
int tree[N + 5];
void add(int x, int k) {
  for (int i = x; i <= dcnt; i += i & (-i)) tree[i] += k;
}
int sum(int x) {
  int r = 0;
  for (int i = x; i; i -= i & (-i)) r += tree[i];
  return r;
}
int val[N + 5];
bool check(const node &k) {
  return val[k.x] >= k.l || sum(dr[k.x]) - sum(dl[k.x]);
}
void update(const node &k) {
  val[k.x] = std::max(val[k.x], k.l), add(dl[k.x], 1);
}
node g[N + 5];
int f[N + 5], n;
char s[N + 5];
int main() {
  scanf("%d", &n), scanf("%s", s);
  lst = rt = ncnt = 1;
  for (int i = n - 1; i >= 0; i--) extend(s[i] - 'a');
  for (int i = 2; i <= ncnt; i++) v[fa[i]].push_back(i);
  dfs(rt);
  node p = (node){rt, 0};
  for (int l = n - 1, r = n - 1; l >= 0; l--) {
    node q = p;
    p = nxt(p, s[l] - 'a');
    while (l < r && !check(q) && !check(fat(p)))
      p = fat(p), q = fat(q), update(g[r--]);
    g[l] = p, f[l] = r - l + 1;
  }
  printf("%d\n", *std::max_element(f, f + n));
}
