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;
char w[1000050];
int ch[1000050][26], fa[1000050], len[1000050], lst = 1, cnt = 1, pos[1000050];
int head[1000050], to[1000050], nxt[1000050], tot;
int f[22][1000050], Lg[1000050], dp[1000050], ans, dfn[1000050], enp[1000050];
int mx[1000050 << 2], n;
inline void add(int u, int v) {
  to[++tot] = v;
  nxt[tot] = head[u];
  head[u] = tot;
}
void update(int l, int r, int x, int v, int p) {
  mx[p] = max(mx[p], v);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(l, mid, x, v, p << 1);
  else
    update(mid + 1, r, x, v, p << 1 | 1);
}
int query(int l, int r, int x, int y, int p) {
  if (x <= l && y >= r) return mx[p];
  int mid = (l + r) >> 1, re = 0;
  if (x <= mid) re = max(re, query(l, mid, x, y, p << 1));
  if (y > mid) re = max(re, query(mid + 1, r, x, y, p << 1 | 1));
  return re;
}
void insert(int x, int id) {
  int p = lst, np = ++cnt, q, nq;
  lst = 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 = ++cnt;
      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] = lst;
}
void dfs(int x) {
  int i;
  dfn[x] = ++dfn[0];
  f[0][x] = fa[x];
  for (i = 1; (1 << i) <= cnt; i++) f[i][x] = f[i - 1][f[i - 1][x]];
  for (i = head[x]; i; i = nxt[i]) {
    dfs(to[i]);
  }
  enp[x] = dfn[0];
}
int LEN;
int getp(int x, int d) {
  x = pos[x];
  int i;
  for (i = 20; i >= 0; i--) {
    if (f[i][x] && len[f[i][x]] >= d) x = f[i][x];
  }
  return x;
}
bool check(int x, int d) {
  if (d == 1) return 1;
  if (x - d + 1 < 1) return 0;
  int p = getp(x, d - 1);
  if (query(1, cnt, dfn[p], enp[p], 1) >= d - 1) return 1;
  p = getp(x - 1, d - 1);
  if (query(1, cnt, dfn[p], enp[p], 1) >= d - 1) return 1;
  return 0;
}
int main() {
  scanf("%d%s", &n, w + 1);
  reverse(w + 1, w + n + 1);
  int i, j = n;
  for (i = 1; i <= n; i++) insert(w[i] - 'a', i);
  for (i = 2; i <= cnt; i++) add(fa[i], i);
  dfs(1);
  LEN = 0;
  while ((1 << LEN) <= cnt) LEN++;
  for (i = 1, j = 0; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    while (!check(i, dp[i])) {
      dp[i]--;
      j++;
      update(1, cnt, dfn[getp(j, dp[j])], dp[j], 1);
    }
    ans = max(ans, dp[i]);
  }
  printf("%d\n", ans);
  return 0;
}
