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 = 5e5 + 10, lg = 20;
const long long int md = 1e9 + 7, b = 727;
int n, ranc[MAXN][lg], a[MAXN], dp[MAXN], seg[MAXN * 4], lc[MAXN][lg];
long long int pw[MAXN], h[MAXN];
string s;
inline void suff_arr() {
  for (int i = 0; i < n; i++) ranc[i][0] = s[i] - 'a';
  vector<pair<pair<int, int>, int>> vec;
  for (int i = 0; i < lg - 1; i++) {
    vec.clear();
    for (int j = 0; j < n; j++) {
      if ((1 << i) + j < n)
        vec.push_back({{ranc[j][i], ranc[(1 << i) + j][i]}, j});
      else
        vec.push_back({{ranc[j][i], -1}, j});
    }
    sort(vec.begin(), vec.end());
    ranc[vec[0].second][i + 1] = 0;
    for (int j = 1; j < n; j++) {
      int x = vec[j].second, lst = vec[j - 1].second;
      ranc[x][i + 1] =
          ranc[lst][i + 1] + 1 - (vec[j].first == vec[j - 1].first);
    }
  }
  for (int i = 0; i < n; i++) a[ranc[i][lg - 1]] = i;
  return;
}
inline long long int get(int l, int r) {
  return (((h[r] - (h[l] * pw[r - l])) % md) + md) % md;
}
inline int lcp(int i, int j) {
  int l = 0, r = n - max(i, j) + 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (get(i, i + mid) == get(j, j + mid))
      l = mid;
    else
      r = mid;
  }
  return l;
}
inline void prep() {
  for (int i = pw[0] = 1; i < MAXN; i++) pw[i] = 1ll * pw[i - 1] * b % md;
  for (int i = 0; i < n; i++) h[i + 1] = ((h[i] * b) + s[i]) % md;
  for (int i = n - 2; i >= 0; i--) {
    lc[i][0] = lcp(a[i], a[i + 1]);
    for (int j = 1; j < lg && i + (1 << (j - 1)) < n; j++)
      lc[i][j] = min(lc[i][j - 1], lc[i + (1 << (j - 1))][j - 1]);
  }
  return;
}
void add(int x, int val, int b = 0, int e = n, int ind = 1) {
  seg[ind] = max(seg[ind], val);
  if (b + 1 == e) return;
  int mid = (b + e) / 2;
  if (x < mid)
    add(x, val, b, mid, ind * 2);
  else
    add(x, val, mid, e, ind * 2 + 1);
  return;
}
int mx(int l, int r, int b = 0, int e = n, int ind = 1) {
  if (l <= b && r >= e) return seg[ind];
  int mid = (b + e) / 2, ret = 0;
  if (l < mid) ret = max(ret, mx(l, r, b, mid, ind * 2));
  if (r > mid) ret = max(ret, mx(l, r, mid, e, ind * 2 + 1));
  return ret;
}
inline bool ok(int i, int k) {
  int l, r;
  l = r = ranc[i][lg - 1];
  for (int j = lg - 1; j >= 0; j--) {
    if (r + (1 << j) < n && lc[r][j] >= k) r += (1 << j);
    if (l >= (1 << j) && lc[l - (1 << j)][j] >= k) l -= (1 << j);
  }
  return (mx(l, r + 1) >= k);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> s;
  suff_arr();
  prep();
  int ans = 1;
  dp[n - 1] = 1;
  for (int i = n - 2; i >= 0; i--) {
    dp[i] = dp[i + 1] + 1;
    while (dp[i] > 1 && !ok(i, dp[i] - 1) && !ok(i + 1, dp[i] - 1)) {
      dp[i]--;
      add(ranc[i + dp[i]][lg - 1], dp[i + dp[i]]);
    }
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n';
  return 0;
}
