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;
int N, M, num, rak[500010], sa[500010], tax[500010], tmp[500010],
    height[500010];
int Log[500010], Min[19][500010], Max[20000010], lson[20000010], rson[20000010],
    root[500010], cnt;
char s[500010], ch;
inline int min(const int &g, const int &h) { return g < h ? g : h; }
inline int max(const int &g, const int &h) { return g > h ? g : h; }
void rsort() {
  for (int i = 1; i <= M; i++) tax[i] = 0;
  for (int i = 1; i <= N; i++) tax[rak[i]]++;
  for (int i = 1; i <= M; i++) tax[i] += tax[i - 1];
  for (int i = N; i >= 1; i--) sa[tax[rak[tmp[i]]]--] = tmp[i];
}
void Init() {
  for (int i = 1; i <= N; i++) rak[i] = s[i] - 'a' + 1, tmp[i] = i;
  M = 26;
  rsort();
  for (int len = 1, p = 0; p < N; M = p, len <<= 1) {
    num = 0;
    for (int i = N - len + 1; i <= N; i++) tmp[++num] = i;
    for (int i = 1; i <= N; i++)
      if (sa[i] > len) tmp[++num] = sa[i] - len;
    rsort();
    swap(tmp, rak);
    rak[sa[1]] = p = 1;
    for (int i = 2; i <= N; i++)
      rak[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] &&
                            tmp[sa[i] + len] == tmp[sa[i - 1] + len]
                        ? p
                        : ++p);
  }
  int e = 0;
  for (int i = 1; i <= N; i++) {
    if (e) e--;
    int j = sa[rak[i] - 1];
    while (s[i + e] == s[j + e]) e++;
    height[rak[i]] = e;
  }
  for (int i = 2; i <= N; i++) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= N; i++) Min[0][i] = height[i];
  for (int k = 1; (1 << k) <= N; k++) {
    for (int i = 1; i + (1 << k) - 1 <= N; i++)
      Min[k][i] = min(Min[k - 1][i], Min[k - 1][i + (1 << (k - 1))]);
  }
}
inline int MIN(const int &l, const int &r) {
  int t = Log[r - l + 1];
  return min(Min[t][l], Min[t][r - (1 << t) + 1]);
}
int modify(int pre, int l, int r, int pos, int ins) {
  int now = ++cnt;
  lson[now] = lson[pre], rson[now] = rson[pre], Max[now] = max(ins, Max[pre]);
  if (l == r) return now;
  int Mid = (l + r) >> 1;
  if (pos <= Mid)
    lson[now] = modify(lson[pre], l, Mid, pos, ins);
  else
    rson[now] = modify(rson[pre], Mid + 1, r, pos, ins);
  return now;
}
int query(int u, int l, int r, int Left, int Right) {
  if (Left <= l && r <= Right) return Max[u];
  int Mid = (l + r) >> 1, ret = 0;
  if (Left <= Mid) ret = max(ret, query(lson[u], l, Mid, Left, Right));
  if (Right > Mid) ret = max(ret, query(rson[u], Mid + 1, r, Left, Right));
  return ret;
}
inline int lfind(const int &pos, const int &lim) {
  int ans = pos;
  for (int k = 18; k >= 0; k--)
    if (ans - (1 << k) >= 1 && MIN(ans - (1 << k) + 1, pos) >= lim)
      ans -= 1 << k;
  return ans;
}
inline int rfind(const int &pos, const int &lim) {
  int ans = pos;
  for (int k = 18; k >= 0; k--)
    if (ans + (1 << k) <= N && MIN(pos + 1, ans + (1 << k)) >= lim)
      ans += 1 << k;
  return ans;
}
inline bool check(int i, int ans) {
  int a = rak[i], b = rak[i + 1];
  return query(root[i + ans], 1, N, lfind(a, ans - 1), rfind(a, ans - 1)) >=
             ans - 1 ||
         query(root[i + ans], 1, N, lfind(b, ans - 1), rfind(b, ans - 1)) >=
             ans - 1;
}
int main() {
  scanf("%d", &N);
  scanf("%s", s + 1);
  Init();
  int ans = 1, res = 1;
  root[N] = modify(0, 1, N, rak[N], 1);
  for (int i = N - 1; i >= 1; i--) {
    ans++;
    while (!check(i, ans)) ans--;
    if (res < ans) res = ans;
    root[i] = modify(root[i + 1], 1, N, rak[i], ans);
  }
  cout << res << endl;
  return 0;
}
