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 + 5;
int n, m, pos[N], dp[N];
char s[N];
vector<int> g[N];
struct SAM {
  int pr[N], son[N][26], len[N], lst, tot;
  SAM() { tot = lst = 1; }
  int extend(int p, int x) {
    int np = ++tot;
    len[np] = len[p] + 1;
    for (; p && !son[p][x]; p = pr[p]) son[p][x] = np;
    if (!p)
      pr[np] = 1;
    else {
      int q = son[p][x];
      if (len[q] == len[p] + 1)
        pr[np] = q;
      else {
        int nq = ++tot;
        for (int i = 0; i <= 25; i++) son[nq][i] = son[q][i];
        pr[nq] = pr[q];
        len[nq] = len[p] + 1;
        pr[np] = pr[q] = nq;
        for (; p && son[p][x] == q; p = pr[p]) son[p][x] = nq;
      }
    }
    return np;
  }
  void build() {
    for (int i = 2; i <= tot; i++) g[pr[i]].push_back(i);
  }
} t;
int tr[N << 2];
void modify(int v, int l, int r, int x, int y) {
  if (l == r) {
    tr[v] = max(tr[v], y);
    return;
  }
  int mid = l + r >> 1;
  if (x <= mid)
    modify(v << 1, l, mid, x, y);
  else
    modify(v << 1 | 1, mid + 1, r, x, y);
  tr[v] = max(tr[v << 1], tr[v << 1 | 1]);
}
int query(int v, int l, int r, int x, int y) {
  if (x <= l && r <= y) return tr[v];
  int mid = l + r >> 1, tmp = 0;
  if (x <= mid) tmp = max(tmp, query(v << 1, l, mid, x, y));
  if (y > mid) tmp = max(tmp, query(v << 1 | 1, mid + 1, r, x, y));
  return tmp;
}
int f[N][20], sz[N], dfn[N], tot;
void dfs(int x) {
  dfn[x] = ++tot;
  sz[x] = 1;
  for (int y : g[x]) f[y][0] = x, dfs(y), sz[x] += sz[y];
}
int get(int x, int d) {
  x = pos[x];
  for (int j = 19; j >= 0; j--)
    if (t.len[f[x][j]] >= d) x = f[x][j];
  return x;
}
bool check(int x, int d) {
  if (d == 1) return 1;
  int p = get(x, d - 1);
  if (query(1, 1, m, dfn[p], dfn[p] + sz[p] - 1) >= d - 1) return 1;
  p = get(x - 1, d - 1);
  if (query(1, 1, m, dfn[p], dfn[p] + sz[p] - 1) >= d - 1) return 1;
  return 0;
}
void insert(int x) {
  int p = get(x, dp[x]);
  modify(1, 1, m, dfn[p], dp[x]);
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; i++) pos[i] = t.lst = t.extend(t.lst, s[i] - 'a');
  t.build();
  dfs(1);
  m = t.tot;
  for (int j = 1; j <= 19; j++)
    for (int i = 1; i <= m; i++) f[i][j] = f[f[i][j - 1]][j - 1];
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    for (; !check(i, dp[i]); dp[i]--) insert(i - dp[i] + 1);
    ans = max(ans, dp[i]);
  }
  printf("%d\n", ans);
  return 0;
}
