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 inf = 0x7fffffff;
const double eps = 1e-10;
const double pi = acos(-1.0);
inline int read() {
  int x = 0, f = 1;
  char ch;
  ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch & 15);
    ch = getchar();
  }
  if (f)
    return x;
  else
    return -x;
}
const int N = 5e5 + 10;
int size = 1, last = 1;
int n, g[N], f[N], ans;
char s[N];
struct Suffix_Automaton {
  int son[26][N << 1], len[N << 1], fa[N << 1];
  void sam(char c) {
    int p = last, np = ++size;
    len[np] = len[p] + 1;
    last = np;
    for (; p && !son[c - 'a'][p]; p = fa[p]) son[c - 'a'][p] = np;
    if (!p)
      fa[np] = 1;
    else {
      int q = son[c - 'a'][p];
      if (len[p] + 1 == len[q])
        fa[np] = q;
      else {
        int nq = ++size;
        len[nq] = len[p] + 1;
        for (int k = 0; k < 26; k++) son[k][nq] = son[k][q];
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        for (; son[c - 'a'][p] == q; p = fa[p]) son[c - 'a'][p] = nq;
      }
    }
  }
  void solve(int i) {
    g[i] = son[s[i] - 'a'][g[i + 1]];
    while (len[fa[g[i]]] >= f[i]) g[i] = fa[g[i]];
  }
} Sam;
struct Segment_Tree {
  int sum[N << 3];
  void update(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && r <= R) {
      if (c > sum[rt]) sum[rt] = c;
      return;
    }
    int mid = l + r >> 1;
    if (L <= mid) update(L, R, c, l, mid, rt << 1);
    if (R > mid) update(L, R, c, mid + 1, r, rt << 1 | 1);
  }
  int query(int id, int l, int r, int rt) {
    if (l == r) return sum[rt];
    int mid = l + r >> 1, ret = sum[rt];
    if (id <= mid)
      ret = max(ret, query(id, l, mid, rt << 1));
    else
      ret = max(ret, query(id, mid + 1, r, rt << 1 | 1));
    return ret;
  }
} Seg;
int S[N << 1], T[N << 1], cnt, l, r;
bool used[N << 1];
int head[N << 1], p;
struct ss {
  int v, last;
} G[N << 1];
void add(int a, int b) {
  G[++p] = (ss){b, head[a]};
  head[a] = p;
}
bool cheak(int x) {
  return (Seg.query(S[l], 1, size, 1) >= x - 1) ||
         (Seg.query(S[r], 1, size, 1) >= x - 1);
}
void dfs(int x) {
  S[x] = ++cnt;
  for (int i = head[x]; i; i = G[i].last) dfs(G[i].v);
  T[x] = cnt;
}
void solve(int x) {
  if (used[x] || x <= 1) return;
  used[x] = 1;
  Seg.update(S[x], T[x], Sam.len[x], 1, size, 1);
  solve(Sam.fa[x]);
}
int main() {
  n = read();
  scanf("%s", s + 1);
  for (int i = n; i >= 1; i--) Sam.sam(s[i]);
  for (int i = 2; i <= size; i++) add(Sam.fa[i], i);
  dfs(1);
  g[n + 1] = l = r = 1;
  for (int i = n; i; i--) {
    r = l, l = Sam.son[s[i] - 'a'][l];
    f[i] = f[i + 1] + 1;
    while (!cheak(f[i])) {
      f[i]--;
      Seg.update(S[g[i + f[i]]], T[g[i + f[i]]], f[i + f[i]], 1, size, 1);
      solve(Sam.fa[g[i + f[i]]]);
    }
    ans = max(ans, f[i]);
    Sam.solve(i);
  }
  printf("%d\n", ans);
  return 0;
}
