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;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
int n, ans, tot = 1, las = 1, root = 1, cnt, pos;
int fa[1000010], len[1000010], ch[1000010][26], bel[1000010], dp[1000010];
int in[1000010], out[1000010], f[1000010][22], mx[4000010];
char s[1000010];
struct edge {
  int to, nxt;
} e[1000010];
int head[1000010], edge_cnt;
void add(int from, int to) {
  e[++edge_cnt] = {to, head[from]}, head[from] = edge_cnt;
}
void modify(int l, int r, int pos, int v, int cur) {
  if (l == r) {
    mx[cur] = v;
    return;
  }
  if (pos <= ((l + r) >> 1))
    modify(l, ((l + r) >> 1), pos, v, (cur << 1));
  else
    modify(((l + r) >> 1) + 1, r, pos, v, (cur << 1 | 1));
  mx[cur] = max(mx[(cur << 1)], mx[(cur << 1 | 1)]);
}
int query(int L, int R, int l, int r, int cur) {
  if (!L || !R) return 0;
  if (L <= l && R >= r) return mx[cur];
  int v = 0;
  if (L <= ((l + r) >> 1))
    v = max(v, query(L, R, l, ((l + r) >> 1), (cur << 1)));
  if (R > ((l + r) >> 1))
    v = max(v, query(L, R, ((l + r) >> 1) + 1, r, (cur << 1 | 1)));
  return v;
}
void insert(int c, int id) {
  int p = las, np = las = ++tot;
  len[np] = len[p] + 1, bel[id] = np;
  while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
  if (!p)
    fa[np] = root;
  else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
      fa[np] = q;
    else {
      int nq = ++tot;
      memcpy(ch[nq], ch[q], sizeof(ch[q]));
      len[nq] = len[p] + 1, fa[nq] = fa[q], fa[np] = fa[q] = nq;
      while (ch[p][c] == q) ch[p][c] = nq, p = fa[p];
    }
  }
}
void dfs(int x) {
  in[x] = ++cnt, f[x][0] = fa[x];
  for (int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
  for (int i = head[x]; i; i = e[i].nxt) dfs(e[i].to);
  out[x] = cnt;
}
int get(int x, int lenth) {
  x = bel[x];
  for (int i = 20; i >= 0; --i)
    if (f[x][i] && len[f[x][i]] >= lenth) x = f[x][i];
  return x;
}
bool check(int p) {
  int x = get(p, dp[p] - 1), y = get(p - 1, dp[p] - 1);
  return max(query(in[x], out[x], 1, tot, root),
             query(in[y], out[y], 1, tot, root)) >= dp[p] - 1;
}
int main() {
  read(n), scanf("%s", s + 1), reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; ++i) insert(s[i] - 'a', i);
  for (int i = 2; i <= tot; ++i) add(fa[i], i);
  dfs(root);
  for (int i = 1; i <= n; ++i) {
    dp[i] = dp[i - 1] + 1;
    while (!check(i))
      dp[i]--, pos++, modify(1, tot, in[bel[pos]], dp[pos], root);
    ans = max(ans, dp[i]);
  }
  printf("%d", ans);
  return 0;
}
