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;
struct edge {
  int v, nxt;
} e[1000005 << 1];
int pp[1000005], eid;
void init() {
  memset(pp, -1, sizeof pp);
  eid = 0;
}
void add(int u, int v) {
  e[eid].v = v;
  e[eid].nxt = pp[u];
  pp[u] = eid++;
}
int ma[1000005 << 2];
void change(int rt, int l, int r, int x, int o) {
  ma[rt] = max(ma[rt], o);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    change(rt << 1, l, mid, x, o);
  else
    change(rt << 1 | 1, mid + 1, r, x, o);
}
int query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) return ma[rt];
  int mid = (l + r) >> 1, ret = 0;
  if (L <= mid) ret = max(ret, query(rt << 1, l, mid, L, R));
  if (R > mid) ret = max(ret, query(rt << 1 | 1, mid + 1, r, L, R));
  return ret;
}
int n, lastt = 1, tot = 1, sz = 0, fa[1000005], ch[1000005][27], f[1000005][23],
       len[1000005], pos[1000005], dfn[1000005], enp[1000005], dp[1000005];
void insert(int x, int id) {
  int p = lastt, np = ++tot, q = 0, nq = 0;
  lastt = np;
  len[np] = len[p] + 1;
  for (; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
  if (!p)
    fa[np] = 1;
  else {
    q = ch[p][x];
    if (len[q] == len[p] + 1)
      fa[np] = q;
    else {
      nq = ++tot;
      fa[nq] = fa[q];
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      fa[q] = fa[np] = nq;
      len[nq] = len[p] + 1;
      for (; p && ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
    }
  }
  pos[id] = lastt;
}
void dfs(int u) {
  dfn[u] = ++sz;
  f[u][0] = fa[u];
  for (int i = 1; (1 << i) <= tot; i++) f[u][i] = f[f[u][i - 1]][i - 1];
  for (int i = pp[u]; i + 1; i = e[i].nxt) {
    dfs(e[i].v);
  }
  enp[u] = sz;
}
int getp(int x, int d) {
  x = pos[x];
  for (int i = 20; i >= 0; i--)
    if (f[x][i] && len[f[x][i]] >= d) x = f[x][i];
  return x;
}
int check(int x, int d) {
  if (d == 1) return 1;
  if (x - d < 0) return 0;
  int p = getp(x, d - 1);
  if (query(1, 1, tot, dfn[p], enp[p]) >= d - 1) return 1;
  p = getp(x - 1, d - 1);
  if (query(1, 1, tot, dfn[p], enp[p]) >= d - 1) return 1;
  return 0;
}
char st[1000005];
int main() {
  init();
  scanf("%d", &n);
  scanf("%s", st + 1);
  for (int i = 1; i <= n / 2; i++) swap(st[i], st[n - i + 1]);
  for (int i = 1; i <= n; i++) insert(st[i] - 'a', i);
  for (int i = 2; i <= tot; i++) add(fa[i], i);
  dfs(1);
  int ans = 0;
  for (int i = 1, j = 0; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    while (!check(i, dp[i])) {
      dp[i]--;
      j++;
      change(1, 1, tot, dfn[getp(j, dp[j])], dp[j]);
    }
    ans = max(ans, dp[i]);
  }
  printf("%d", ans);
  return 0;
}
