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;
struct Node {
  Node *lch, *rch;
  int l, r, mx;
} * rt;
Node *Build(int l, int r) {
  Node *ret = new Node;
  ret->l = l;
  ret->r = r;
  ret->mx = 0;
  if (l == r) {
    ret->lch = ret->rch = NULL;
    return ret;
  }
  int mid = (l + r) >> 1;
  ret->lch = Build(l, mid);
  ret->rch = Build(mid + 1, r);
  return ret;
}
void modify(Node *x, int p, int v) {
  x->mx = max(x->mx, v);
  if (x->l == x->r) return;
  int mid = (x->l + x->r) >> 1;
  if (p <= mid)
    modify(x->lch, p, v);
  else
    modify(x->rch, p, v);
}
int query(Node *x, int l, int r) {
  if (l <= x->l && r >= x->r) return x->mx;
  int mid = (x->l + x->r) >> 1, ret = 0;
  if (l <= mid) ret = max(ret, query(x->lch, l, r));
  if (mid < r) ret = max(ret, query(x->rch, l, r));
  return ret;
}
char s[505050];
int dp[505050];
int h[505050], t[505050];
int x[505050], y[505050], sa[505050];
int lg[505050];
int mi[20][505050];
int n;
int lcp(int a, int b) {
  if (a > b) swap(a, b);
  if (a < 0 || b >= n) return 0;
  if (a == b) return n;
  a++;
  return min(mi[lg[b - a]][a], mi[lg[b - a]][b - (1 << lg[b - a]) + 1]);
}
bool work(int p, int k) {
  if (p == n) return false;
  int rk = x[p];
  int l = rk, r = n - 1, mid, h1, h2;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (lcp(rk, mid) >= k)
      l = mid;
    else
      r = mid - 1;
  }
  h2 = l;
  l = 0;
  r = rk;
  while (l < r) {
    mid = (l + r) >> 1;
    if (lcp(rk, mid) >= k)
      r = mid;
    else
      l = mid + 1;
  }
  h1 = l;
  return query(rt, h1, h2) >= k;
}
int main() {
  int m = 300, ans = 0;
  scanf("%d", &n);
  scanf("%s", s);
  memset(t, 0, sizeof(t));
  for (int i = 0; i < n; i++) t[x[i] = s[i]]++;
  x[n] = y[n] = -1;
  for (int i = 1; i < m; i++) t[i] += t[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--t[x[i]]] = i;
  for (int i = 1;; i <<= 1) {
    int p = 0;
    for (int j = n - i; j < n; j++) y[p++] = j;
    for (int j = 0; j < n; j++)
      if (sa[j] >= i) y[p++] = sa[j] - i;
    for (int j = 0; j < m; j++) t[j] = 0;
    for (int j = 0; j < n; j++) t[x[j]]++;
    for (int j = 1; j < m; j++) t[j] += t[j - 1];
    for (int j = n - 1; j >= 0; j--) sa[--t[x[y[j]]]] = y[j];
    swap(x, y);
    m = 0;
    x[sa[0]] = 0;
    for (int j = 1; j < n; j++)
      if (y[sa[j]] == y[sa[j - 1]] && y[sa[j] + i] == y[sa[j - 1] + i])
        x[sa[j]] = m;
      else
        x[sa[j]] = ++m;
    m++;
    if (m == n) break;
  }
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (x[i] == 0) {
      h[0] = 0;
      k = 0;
      continue;
    }
    while (s[i + k] == s[sa[x[i] - 1] + k]) k++;
    h[x[i]] = k;
    if (k) k--;
  }
  for (int i = 1; i < n; i++) mi[0][i] = h[i];
  lg[0] = lg[1] = 0;
  for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= 18; i++)
    for (int j = n - (1 << i); j >= 0; j--)
      mi[i][j] = min(mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]);
  k = 0;
  rt = Build(0, n - 1);
  for (int i = n - 1; i >= 0; i--) {
    while ((!work(i, k)) && (!work(i + 1, k))) {
      modify(rt, x[i + k], dp[i + k]);
      k--;
    }
    dp[i] = ++k;
    ans = max(ans, dp[i]);
  }
  printf("%d", ans);
  return 0;
}
