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 + 10;
int n;
char str[N];
namespace SA {
int ary[4][N], *sa, *nsa, *rnk, *nrnk;
int ton[N];
int hei[N], Lmn[N][20], Rmn[N][20];
void Build() {
  sa = ary[0], nsa = ary[1], rnk = ary[2], nrnk = ary[3];
  for (int i = 1; i <= n; i++) ton[str[i] - 'a']++;
  for (int i = 1; i < 26; i++) ton[i] += ton[i - 1];
  for (int i = 1; i <= n; i++) sa[ton[str[i] - 'a']--] = i;
  rnk[sa[1]] = 1;
  for (int i = 2; i <= n; i++) {
    rnk[sa[i]] = rnk[sa[i - 1]];
    if (str[sa[i]] != str[sa[i - 1]]) rnk[sa[i]]++;
  }
  for (int L = 1; rnk[sa[n]] < n; L <<= 1) {
    for (int i = 1; i <= n; i++) ton[rnk[sa[i]]] = i;
    for (int i = n; i >= 1; i--)
      if (sa[i] - L >= 1) nsa[ton[rnk[sa[i] - L]]--] = sa[i] - L;
    for (int i = n - L + 1; i <= n; i++) nsa[ton[rnk[i]]--] = i;
    nrnk[nsa[1]] = 1;
    for (int i = 2; i <= n; i++) {
      nrnk[nsa[i]] = nrnk[nsa[i - 1]];
      if ((nsa[i] <= n ? rnk[nsa[i]] : -1) !=
              (nsa[i - 1] <= n ? rnk[nsa[i - 1]] : -1) ||
          (nsa[i] + L <= n ? rnk[nsa[i] + L] : -1) !=
              (nsa[i - 1] + L <= n ? rnk[nsa[i - 1] + L] : -1))
        nrnk[nsa[i]]++;
    }
    swap(rnk, nrnk), swap(sa, nsa);
  }
  for (int i = 1, tmp = 0; i <= n; i++) {
    if (tmp) tmp--;
    while (str[i + tmp] == str[sa[rnk[i] - 1] + tmp]) tmp++;
    hei[rnk[i]] = tmp;
  }
}
void RBuild() {
  for (int i = 2; i <= n; i++) {
    Lmn[i][0] = hei[i];
    for (int j = 1; j < 20; j++)
      if (i - (1 << (j - 1)) >= 1)
        Lmn[i][j] = min(Lmn[i][j - 1], Lmn[i - (1 << (j - 1))][j - 1]);
      else
        Lmn[i][j] = 0;
  }
  for (int i = n; i >= 2; i--) {
    Rmn[i][0] = hei[i];
    for (int j = 1; j < 20; j++)
      if (i + (1 << (j - 1)) >= 1)
        Rmn[i][j] = min(Rmn[i][j - 1], Rmn[i + (1 << (j - 1))][j - 1]);
      else
        Rmn[i][j] = 0;
  }
}
}  // namespace SA
struct SEGTREE {
  int mx[N << 1];
  void PushUp(const int& le, const int& ri) {
    int mi = (le + ri) >> 1;
    mx[(((le) + (ri)) | ((le) != (ri)))] =
        max(mx[(((le) + (mi)) | ((le) != (mi)))],
            mx[(((mi + 1) + (ri)) | ((mi + 1) != (ri)))]);
  }
  void Modify(const int& le, const int& ri, const int& po, const int& key) {
    if (le == ri) {
      mx[(((le) + (ri)) | ((le) != (ri)))] = key;
      return;
    }
    int mi = (le + ri) >> 1;
    if (po <= mi)
      Modify(le, mi, po, key);
    else
      Modify(mi + 1, ri, po, key);
    PushUp(le, ri);
  }
  int Query(const int& le, const int& ri, const int& Le, const int& Ri) {
    if (Le <= le && ri <= Ri) return mx[(((le) + (ri)) | ((le) != (ri)))];
    int mi = (le + ri) >> 1;
    if (Ri <= mi) return Query(le, mi, Le, Ri);
    if (mi < Le) return Query(mi + 1, ri, Le, Ri);
    return max(Query(le, mi, Le, Ri), Query(mi + 1, ri, Le, Ri));
  }
} Se;
pair<int, int> Bound(const int& p, const int& len) {
  int L = p, R = p + 1;
  for (int i = 19; i >= 0; i--) {
    if (SA::Lmn[L][i] >= len) L -= (1 << i);
    if (SA::Rmn[R][i] >= len) R += (1 << i);
  }
  return make_pair(L, R - 1);
}
int dp[N];
int main() {
  scanf("%d%s", &n, str + 1);
  SA::Build();
  SA::RBuild();
  int ans = 0;
  for (int i = n, cur = n; i >= 1; i--) {
    while (cur > i) {
      pair<int, int> res1 = Bound(SA::rnk[i], cur - i),
                     res2 = Bound(SA::rnk[i + 1], cur - i);
      int tmp = max(Se.Query(1, n, res2.first, res2.second),
                    Se.Query(1, n, res1.first, res1.second));
      if (tmp >= cur - i) break;
      Se.Modify(1, n, SA::rnk[cur], dp[cur]);
      cur--;
    }
    ans = max(ans, dp[i] = cur - i + 1);
  }
  printf("%d\n", ans);
  return 0;
}
