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 + 5, mod = 1e9 + 7, lg = 22;
int n, suf[maxn], lcp[maxn], Rank[lg][maxn], pw2[30], rmq[lg][maxn], lst,
    seg[maxn * 4], klg[maxn], dp[maxn];
string s;
vector<pair<pair<int, int>, int>> V2;
void raDix_Sort() {
  vector<vector<pair<pair<int, int>, int>>> V1(maxn), V3(maxn);
  for (auto i : V2) V1[i.first.second + 1].push_back(i);
  V2.clear();
  for (int i = 0; i <= n; i++)
    for (auto j : V1[i]) V3[j.first.first].push_back(j);
  for (int i = 0; i < n; i++)
    for (auto j : V3[i]) V2.push_back(j);
}
void build_suffix_array() {
  vector<pair<int, int>> V;
  V2.resize(n);
  for (int i = 0; i < n; i++) V.push_back({s[i] - 'a', i});
  sort(V.begin(), V.end());
  for (int i = 1; i < n; i++)
    Rank[0][V[i].second] =
        Rank[0][V[i - 1].second] + ((V[i].first) != (V[i - 1].first));
  for (int i = 0; pw2[i] < n; i++) {
    for (int j = 0; j < n; j++) {
      int x = -1;
      if (j + pw2[i] < n) x = Rank[i][j + pw2[i]];
      V2[j] = {{Rank[i][j], x}, j};
    }
    raDix_Sort();
    Rank[i + 1][V2[0].second] = 0;
    for (int j = 1; j < n; j++)
      Rank[i + 1][V2[j].second] =
          Rank[i + 1][V2[j - 1].second] + ((V2[j].first) != (V2[j - 1].first));
    lst = i + 1;
    if (Rank[i + 1][V2[n - 1].second] == n - 1) break;
  }
  for (int i = 0; i < n; i++) suf[Rank[lst][i]] = i;
  for (int i = 0; i < n - 1; i++) {
    int p1 = suf[i], p2 = suf[i + 1];
    for (int j = lst; j >= 0; j--) {
      if (Rank[j][p1] != Rank[j][p2]) continue;
      if (p1 >= n || p2 >= n) continue;
      p1 += pw2[j];
      p2 += pw2[j];
    }
    lcp[i] = p1 - suf[i];
    rmq[0][i] = lcp[i];
  }
  n--;
  for (int j = 1; j <= klg[n]; j++) {
    for (int i = 0; i <= n - pw2[j]; i++)
      rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + pw2[j - 1]]);
  }
  n++;
}
void fix(int p, int x, int v = 1, int s = 0, int e = n) {
  if (e - s == 1) {
    seg[v] = x;
    return;
  }
  int mid = (e + s) >> 1, lc = v << 1, rc = lc | 1;
  if (mid > p)
    fix(p, x, lc, s, mid);
  else
    fix(p, x, rc, mid, e);
  seg[v] = max(seg[lc], seg[rc]);
}
int get(int l, int r, int v = 1, int s = 0, int e = n) {
  if ((l >= e) || (r <= s)) return 0;
  if ((l <= s) && (e <= r)) return seg[v];
  int mid = (e + s) >> 1, lc = v << 1, rc = lc | 1;
  return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}
int get_mn(int l, int r) {
  return min(rmq[klg[r - l]][l], rmq[klg[r - l]][r - pw2[klg[r - l]]]);
}
bool check(int l, int r) {
  int len = r - l, p = Rank[lst][l], p1, p2, l1 = p, r1 = n;
  while (l1 != r1 - 1) {
    int mid = (l1 + r1) >> 1;
    if (get_mn(l1, mid) >= len)
      l1 = mid;
    else
      r1 = mid;
  }
  p2 = r1;
  l1 = -1;
  r1 = p;
  while (l1 != r1 - 1) {
    int mid = (l1 + r1) >> 1;
    if (get_mn(mid, r1) >= len)
      r1 = mid;
    else
      l1 = mid;
  }
  p1 = r1;
  if (get(p1, p2) >= len)
    return 1;
  else
    return 0;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  pw2[0] = 1;
  klg[1] = 0;
  for (int i = 1; i < 25; i++) pw2[i] = (pw2[i - 1] * 2);
  for (int i = 2; i < maxn; i++)
    klg[i] = klg[i - 1] + (pw2[klg[i - 1]] * 2 == i);
  cin >> n >> s;
  build_suffix_array();
  int ans = 1, l = n - 2, r = n - 1;
  dp[n - 1] = 1;
  fix(Rank[lst][n - 1], 1);
  while (l >= 0) {
    if (l == r - 1) {
      dp[l] = 1;
      l--;
      continue;
    }
    if (!check(l, r - 1)) {
      if (!check(l + 1, r)) {
        r--;
        fix(Rank[lst][r], dp[r]);
        continue;
      }
    }
    ans = max(ans, r - l);
    dp[l] = r - l;
    l--;
  }
  cout << ans << endl;
}
