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 = 1e6 + 50;
int n, las, tr[N][26], l[N], fa[N], head[N], nn[N][2], cnt, tot;
char s[N];
void add(int c) {
  int v = las, u = ++tot;
  l[u] = l[v] + 1, las = u;
  while (!tr[v][c]) tr[v][c] = u, v = fa[v];
  if (tr[v][c] == u) return;
  int x = tr[v][c];
  if (l[x] == l[v] + 1) {
    fa[u] = x;
    return;
  }
  int y = ++tot;
  memcpy(tr[y], tr[x], sizeof(tr[y]));
  l[y] = l[v] + 1, fa[y] = fa[x], fa[x] = fa[u] = y;
  while (tr[v][c] == x) tr[v][c] = y, v = fa[v];
  return;
}
int f[N], bl[N], st[N][20], g[N << 2], L[N], R[N], tim;
void dfs(int x, int fu) {
  st[x][0] = fu, L[x] = ++tim;
  for (int t = 1; t < 20; ++t) st[x][t] = st[st[x][t - 1]][t - 1];
  for (int i = head[x]; i; i = nn[i][0]) dfs(nn[i][1], x);
  R[x] = tim;
  return;
}
int get(int x, int len) {
  x = bl[x];
  for (int t = 19; ~t; --t)
    if (l[st[x][t]] >= len) x = st[x][t];
  return x;
}
int qry(int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return g[x];
  int mid = (l + r) >> 1, ans = 0;
  if (ql <= mid) ans = max(ans, qry(x << 1, l, mid, ql, qr));
  if (qr > mid) ans = max(ans, qry(x << 1 | 1, mid + 1, r, ql, qr));
  return ans;
}
void ins(int x, int l, int r, int y, int s) {
  g[x] = max(g[x], s);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (y <= mid)
    ins(x << 1, l, mid, y, s);
  else
    ins(x << 1 | 1, mid + 1, r, y, s);
  return;
}
int check(int x) {
  if (f[x] == 1) return 1;
  int p = get(x - 1, f[x] - 1), q = get(x, f[x] - 1);
  return qry(1, 1, tot, L[p], R[p]) >= f[x] - 1 ||
         qry(1, 1, tot, L[q], R[q]) >= f[x] - 1;
}
int main() {
  cin >> n, scanf("%s", s + 1), reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; ++i) add(s[i] - 'a'), bl[i] = las;
  for (int i = 1; i <= tot; ++i)
    if (fa[i]) (nn[++cnt][1] = i, nn[cnt][0] = head[fa[i]], head[fa[i]] = cnt);
  for (int i = 1; i <= tot; ++i)
    if (!fa[i]) dfs(i, 0);
  int ans = 0;
  for (int i = 1, j = 0; i <= n; ++i) {
    f[i] = f[i - 1] + 1;
    while (!check(i)) {
      --f[i], ++j;
      ins(1, 1, tot, L[get(j, f[j])], f[j]);
    }
    ans = max(ans, f[i]);
  }
  cout << ans;
  return 0;
}
