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 <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 5e5 + 20;
const int inf = 0x3f3f3f3f;
char str[maxn];
int n;
int x[maxn], y[maxn], tag[maxn], v[maxn << 1], sa[maxn], rk[maxn], ht[maxn];
inline void get_sa() {
  int m = 26;
  for (int i = (1), _end_ = (n); i <= _end_; i++)
    tag[x[i] = str[i] - 'a' + 1]++;
  for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
  for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[x[i]]--] = i;
  for (int j = 1, p = 0; p < n; m = p, j <<= 1) {
    p = 0;
    for (int i = (n - j + 1), _end_ = (n); i <= _end_; i++) y[++p] = i;
    for (int i = (1), _end_ = (n); i <= _end_; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = (0), _end_ = (m); i <= _end_; i++) tag[i] = 0;
    for (int i = (1), _end_ = (n); i <= _end_; i++) tag[v[i] = x[y[i]]]++;
    for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
    for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[v[i]]--] = y[i];
    p = 1;
    for (int i = (1), _end_ = (n); i <= _end_; i++) v[i] = x[i];
    x[sa[1]] = 1;
    for (int i = (2), _end_ = (n); i <= _end_; i++)
      x[sa[i]] = v[sa[i]] == v[sa[i - 1]] && v[sa[i] + j] == v[sa[i - 1] + j]
                     ? p
                     : ++p;
  }
  for (int i = (1), _end_ = (n); i <= _end_; i++) rk[sa[i]] = i;
  int j = 0;
  for (int i = (1), _end_ = (n); i <= _end_; i++) {
    if (j) j--;
    if (rk[i] == n) continue;
    while (i + j <= n && sa[rk[i] + 1] + j <= n &&
           str[i + j] == str[sa[rk[i] + 1] + j])
      j++;
    ht[rk[i]] = j;
  }
}
inline void init() {
  n = read();
  scanf("%s", str + 1);
  get_sa();
}
struct node {
  int mx;
  int ht;
  inline void Merge(node lc, node rc) { mx = max(lc.mx, rc.mx); }
};
node c[maxn << 2];
void make_tree(int o, int l, int r) {
  if (l == r) return c[o].ht = ht[l], void();
  int mid = (l + r) >> 1;
  make_tree((o << 1), l, mid);
  make_tree((o << 1 | 1), mid + 1, r);
  c[o].ht = min(c[(o << 1)].ht, c[(o << 1 | 1)].ht);
}
int dp[maxn];
int queryR(int ql, int qr, int &mn, int d, int o, int l, int r) {
  if (ql > qr) return 0;
  if (ql <= l && r <= qr) {
    if (c[o].ht >= d) return chkmin(mn, c[o].ht), c[o].mx;
    if (l == r) return chkmin(mn, c[o].ht), 0;
  }
  int mid = (l + r) >> 1, ans = 0;
  if (qr > mid) {
    chkmax(ans, queryR(ql, qr, mn, d, (o << 1 | 1), mid + 1, r));
    if (mn < d) return ans;
  }
  if (ql <= mid) {
    chkmax(ans, queryR(ql, qr, mn, d, (o << 1), l, mid));
  }
  return ans;
}
int queryL(int ql, int qr, int &mn, int d, int o, int l, int r) {
  if (ql > qr) return 0;
  if (ql <= l && r <= qr) {
    if (c[o].ht >= d) return chkmin(mn, c[o].ht), c[o].mx;
    if (l == r) return chkmin(mn, c[o].ht), c[o].mx;
  }
  int mid = (l + r) >> 1, ans = 0;
  if (ql <= mid) {
    chkmax(ans, queryL(ql, qr, mn, d, (o << 1), l, mid));
    if (mn < d) return ans;
  }
  if (qr > mid) {
    chkmax(ans, queryL(ql, qr, mn, d, (o << 1 | 1), mid + 1, r));
  }
  return ans;
}
void update(int x, int d, int o, int l, int r) {
  if (l == r) return chkmax(c[o].mx, d), void();
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(x, d, (o << 1), l, mid);
  else
    update(x, d, (o << 1 | 1), mid + 1, r);
  c[o].Merge(c[(o << 1)], c[(o << 1 | 1)]);
}
inline void doing() {
  int ans = 1, Ans = ans;
  dp[n] = 1;
  make_tree(1, 1, n);
  for (int i = (n - 1), _end_ = (1); i >= _end_; i--) {
    ++ans;
    int tmp = 0, t = inf, t1 = inf;
    do {
      t = t1 = inf;
      tmp = max(queryR(1, rk[i + 1] - 1, t, ans - 1, 1, 1, n),
                queryL(rk[i + 1], n, t1, ans - 1, 1, 1, n)) +
            1;
      t = t1 = inf;
      chkmax(tmp, max(queryR(1, rk[i] - 1, t, ans - 1, 1, 1, n),
                      queryL(rk[i], n, t1, ans - 1, 1, 1, n)) +
                      1);
      if (tmp < ans) {
        ans--;
        update(rk[i + ans], dp[i + ans], 1, 1, n);
      } else
        break;
    } while (1);
    dp[i] = ans;
    chkmax(Ans, ans);
  }
  printf("%d\n", Ans);
}
int main() {
  init();
  doing();
  return 0;
}
