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 maxn = 500005;
const int maxlogn = 23;
const int maxnode = maxn * maxlogn;
int n, sa[maxn], rk[maxn], sz[maxn], maxx[maxn], ans;
int h[maxlogn][maxn], logn;
int rt[maxn], lc[maxnode], rc[maxnode], tot, val[maxnode];
char s[maxn];
void build(int &rt, int l, int r) {
  rt = ++tot, val[rt] = 0, lc[rt] = rc[rt] = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(lc[rt], l, mid), build(rc[rt], mid + 1, r);
}
void build(int &rt, int pre, int l, int r, int x, int y) {
  rt = ++tot, val[rt] = max(val[pre], y), lc[rt] = lc[pre], rc[rt] = rc[pre];
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    build(lc[rt], lc[pre], l, mid, x, y);
  else
    build(rc[rt], rc[pre], mid + 1, r, x, y);
}
int query(int rt, int l, int r, int x, int y) {
  if (x <= l && r <= y) return val[rt];
  int mid = (l + r) >> 1, res = 0;
  if (x <= mid) res = max(res, query(lc[rt], l, mid, x, y));
  if (mid < y) res = max(res, query(rc[rt], mid + 1, r, x, y));
  return res;
}
bool query1(int rt, int l, int r, int x, int y, int z) {
  if (x <= l && r <= y) return val[rt] >= z;
  if (val[rt] < z) return false;
  int mid = (l + r) >> 1;
  if (x <= mid)
    if (query1(lc[rt], l, mid, x, y, z)) return true;
  if (mid < y)
    if (query1(rc[rt], mid + 1, r, x, y, z)) return true;
  return false;
}
int main() {
  int m = 128, k, p, *x = h[0], *y = rk, i, l, r, mid, L, R;
  scanf("%d%s", &n, s);
  for (i = 0; i < m; i++) sz[i] = 0;
  for (i = 0; i < n; i++) sz[x[i] = s[i]]++;
  for (i = 1; i < m; i++) sz[i] += sz[i - 1];
  for (i = 0; i < n; i++) sa[--sz[x[i]]] = i;
  for (k = 1;; k <<= 1) {
    for (i = n - k, p = 0; i < n; i++) y[p++] = i;
    for (i = 0; i < n; i++)
      if (sa[i] >= k) y[p++] = sa[i] - k;
    for (i = 0; i < m; i++) sz[i] = 0;
    for (i = 0; i < n; i++) sz[x[i]]++;
    for (i = 1; i < m; i++) sz[i] += sz[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--sz[x[y[i]]]] = y[i];
    swap(x, y);
    for (i = 1, x[sa[0]] = 0, m = 1; i < n; i++)
      x[sa[i]] =
          (y[sa[i]] == y[sa[i - 1]] && (sa[i] < n - k) == (sa[i - 1] < n - k) &&
           (sa[i] >= n - k || y[sa[i] + k] == y[sa[i - 1] + k]))
              ? m - 1
              : (m++);
    if (m >= n) break;
  }
  for (i = 0; i < n; i++) rk[sa[i]] = i;
  for (h[0][0] = 0, i = 0, p = 0; i < n; i++) {
    if (p) p--;
    if (!rk[i]) continue;
    while (s[i + p] == s[sa[rk[i] - 1] + p]) p++;
    h[0][rk[i]] = p;
  }
  for (logn = 0; (1 << logn) <= n; logn++)
    ;
  for (i = 1; i <= logn; i++)
    for (p = 0; p + (1 << i) <= n; p++)
      h[i][p] = min(h[i - 1][p], h[i - 1][p + (1 << (i - 1))]);
  ans = 1;
  for (i = 0; i < n; i++) maxx[i] = 1;
  tot = 1, val[0] = 0, lc[0] = rc[0] = 0, build(rt[n], 0, n - 1);
  for (i = n - 1; i >= 0; ans = max(ans, maxx[i]), i--) {
    l = 1, r = n - i;
    while (l < r) {
      mid = (l + r + 1) >> 1;
      if (i + mid * (long long)(mid + 1) / 2 > n + 5) {
        r = mid - 1;
        continue;
      }
      L = R = rk[i];
      for (p = logn; p >= 0; p--)
        if (R + (1 << p) < n && h[p][R + 1] >= mid - 1) R += 1 << p;
      for (p = logn; p >= 0; p--)
        if (L - (1 << p) >= 0 && h[p][L - (1 << p) + 1] >= mid - 1) L -= 1 << p;
      if (query1(rt[i + mid], 0, n - 1, L, R, mid - 1))
        l = mid;
      else
        r = mid - 1;
    }
    maxx[i] = max(maxx[i], l);
    if (!i) continue;
    l = 0, r = n - i;
    while (l < r) {
      mid = (l + r + 1) >> 1;
      if (i + mid * (long long)(mid + 1) / 2 > n + 5) {
        r = mid - 1;
        continue;
      }
      L = R = rk[i];
      for (p = logn; p >= 0; p--)
        if (R + (1 << p) < n && h[p][R + 1] >= mid) R += 1 << p;
      for (p = logn; p >= 0; p--)
        if (L - (1 << p) >= 0 && h[p][L - (1 << p) + 1] >= mid) L -= 1 << p;
      if (query1(rt[i + mid], 0, n - 1, L, R, mid))
        l = mid;
      else
        r = mid - 1;
    }
    maxx[i - 1] = max(maxx[i - 1], l + 1);
    build(rt[i], rt[i + 1], 0, n - 1, rk[i], maxx[i]);
  }
  printf("%d\n", ans);
  return 0;
}
