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 = 5e5 + 10, MOD = 1e9 + 7;
int ord[N], pos[N], rnk[19][N], L[19][N], R[19][N], dp[N], seg[N << 2], n;
char second[N];
void modify(int p, int x, int id = 1, int l = 1, int r = n + 1) {
  if (r - l < 2) {
    seg[id] = x;
    return;
  }
  int md = (l + r) >> 1;
  if (p < md)
    modify(p, x, id << 1, l, md);
  else
    modify(p, x, id << 1 | 1, md, r);
  seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
int get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
  if (qr <= l || r <= ql) return 0;
  if (ql <= l && r <= qr) return seg[id];
  int md = (l + r) >> 1;
  return max(get(ql, qr, id << 1, l, md), get(ql, qr, id << 1 | 1, md, r));
}
void buildSA() {
  for (int i = 1; i <= n; i++) rnk[0][i] = second[i] - 'a', ord[i] = i;
  for (int pw = 0; pw < 18; pw++) {
    auto cmp = [&](const int &x, const int &y) {
      if (rnk[pw][x] != rnk[pw][y]) return rnk[pw][x] < rnk[pw][y];
      if (max(x, y) + (1 << pw) > n + 1) return x > y;
      return rnk[pw][x + (1 << pw)] < rnk[pw][y + (1 << pw)];
    };
    sort(ord + 1, ord + n + 1, cmp);
    for (int i = 2; i <= n; i++)
      rnk[pw + 1][ord[i]] = rnk[pw + 1][ord[i - 1]] + cmp(ord[i - 1], ord[i]);
  }
}
int LCP(int x, int y) {
  if (x > y) swap(x, y);
  int ret = 0;
  for (int i = 19; i--;)
    if (y + (1 << i) <= n + 1 && rnk[i][x] == rnk[i][y]) {
      ret ^= (1 << i);
      x += (1 << i);
      y += (1 << i);
    }
  return ret;
}
int check(int p, int x) {
  int l = p, r = p;
  for (int i = 19; i--;) {
    if (r + (1 << i) <= n + 1 && L[i][r] >= x) r += 1 << i;
    if (l - (1 << i) > -1 && R[i][l] >= x) l -= 1 << i;
  }
  return get(l, r + 1) >= x;
}
int main() {
  scanf("%d%s", &n, second + 1);
  buildSA();
  for (int i = 1; i <= n; i++) pos[ord[i]] = i;
  for (int i = 1; i <= n; i++) {
    if (i < n) L[0][i] = LCP(ord[i], ord[i + 1]);
    if (i > 1) R[0][i] = LCP(ord[i], ord[i - 1]);
  }
  for (int j = 0; j + 1 < 19; j++) {
    for (int i = 1; i <= n; i++)
      if (i + (1 << (j + 1)) <= n + 1) {
        L[j + 1][i] = min(L[j][i], L[j][i + (1 << j)]);
      }
    for (int i = 1; i <= n; i++)
      if (i - (1 << (j + 1)) > -1) {
        R[j + 1][i] = min(R[j][i], R[j][i - (1 << j)]);
      }
  }
  dp[n] = 1;
  int ptr = n;
  for (int i = n - 1; i; i--) {
    for (dp[i] = dp[i + 1] + 1;; dp[i]--) {
      for (; i + dp[i] <= ptr; ptr--) modify(pos[ptr], dp[ptr]);
      if (check(pos[i], dp[i] - 1) || check(pos[i + 1], dp[i] - 1)) break;
    }
  }
  printf("%d\n", *max_element(dp, dp + N));
  return 0;
}
