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 = 500005;
int n, f[maxn], sa[maxn], tax[maxn], rnk[maxn], tp[maxn], h[maxn], lg[maxn],
    st[maxn][20];
char s[maxn];
inline void SA() {
  int m = 128, i, j, k, p, f = 0;
  for (i = 1; i <= n; i++) rnk[i] = s[i];
  for (i = 1; i <= n; i++) tax[rnk[i]]++;
  for (i = 1; i <= m; i++) tax[i] += tax[i - 1];
  for (i = n; i >= 1; i--) sa[tax[rnk[i]]--] = i;
  for (k = 1, p = 0; k < n; k <<= 1, m = p) {
    p = 0;
    for (i = n - k + 1; i <= n; i++) tp[++p] = i;
    for (i = 1; i <= n; i++)
      if (sa[i] > k) tp[++p] = sa[i] - k;
    for (i = 1; i <= m; i++) tax[i] = 0;
    for (i = 1; i <= n; i++) tax[rnk[i]]++;
    for (i = 1; i <= m; i++) tax[i] += tax[i - 1];
    for (i = n; i >= 1; i--) sa[tax[rnk[tp[i]]]--] = tp[i];
    for (i = 1; i <= n; i++) swap(rnk[i], tp[i]);
    rnk[sa[1]] = p = 1;
    for (i = 2; i <= n; i++)
      rnk[sa[i]] =
          (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + k] == tp[sa[i] + k])
              ? p
              : ++p;
  }
  for (i = 1; i <= n; i++) rnk[sa[i]] = i;
  for (i = 1; i <= n; i++) {
    p = sa[rnk[i] - 1];
    if (f) f--;
    while (s[i + f] == s[p + f]) f++;
    h[rnk[i]] = f;
  }
  for (i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  for (i = 1; i <= n; i++) st[i][0] = h[i];
  for (j = 1; j <= 19; j++)
    for (i = 1; i <= n - (1 << j) + 1; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
inline int LCP(int l, int r) {
  if (l == r) return n - sa[l] + 1;
  l++;
  int k = lg[r - l + 1];
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}
inline int getleft(int k, int val) {
  int l = 1, r = k, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (LCP(mid, k) >= val)
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  return ans;
}
inline int getright(int k, int val) {
  int l = k, r = n, mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (LCP(k, mid) >= val)
      l = mid + 1, ans = mid;
    else
      r = mid - 1;
  }
  return ans;
}
struct Segment_Tree {
  int mx[maxn << 2];
  void update(int rt, int l, int r, int u, int v) {
    if (l == r) {
      mx[rt] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (u <= mid)
      update((rt << 1), l, mid, u, v);
    else
      update((rt << 1 | 1), mid + 1, r, u, v);
    mx[rt] = max(mx[(rt << 1)], mx[(rt << 1 | 1)]);
  }
  int query(int rt, int l, int r, int x, int y) {
    if (x <= l && r <= y) return mx[rt];
    int mid = (l + r) >> 1, ans = 0;
    if (x <= mid) ans = max(ans, query((rt << 1), l, mid, x, y));
    if (y > mid) ans = max(ans, query((rt << 1 | 1), mid + 1, r, x, y));
    return ans;
  }
} T;
inline bool check(int k, int val) {
  if (!k) return false;
  int l = getleft(k, val), r = getright(k, val);
  return T.query(1, 1, n, l, r) >= val;
}
int main() {
  scanf("%d%s", &n, s + 1);
  SA();
  int ans = 0;
  for (int i = n, j = 0; i; i--) {
    j++;
    for (; j > 1; j--) {
      if (i + j > n) continue;
      T.update(1, 1, n, rnk[i + j], f[i + j]);
      if (check(rnk[i], j - 1) || check(rnk[i + 1], j - 1)) break;
    }
    f[i] = j, ans = max(ans, f[i]);
  }
  printf("%d\n", ans);
  return 0;
}
