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;
char a[500005];
int sa[500005], height[500005], cnt[500005], x[500005], tmp1[500005],
    Rank[500005], st[500005][21], lg[500005], maxn[2000005], dp[500005], n, m;
void MakeSuffixArray() {
  m = 127;
  for (int i = 1; i <= n; ++i) ++cnt[x[i] = a[i]];
  for (int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i; --i) sa[cnt[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int tmp = 0;
    for (int i = n - k + 1; i <= n; ++i) tmp1[++tmp] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > k) tmp1[++tmp] = sa[i] - k;
    for (int i = 1; i <= m; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) ++cnt[x[i]];
    for (int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i; --i) sa[cnt[x[tmp1[i]]]--] = tmp1[i], tmp1[i] = 0;
    swap(x, tmp1);
    tmp = 1;
    x[sa[1]] = 1;
    for (int i = 2; i <= n; ++i)
      x[sa[i]] = (tmp1[sa[i]] == tmp1[sa[i - 1]] &&
                  tmp1[sa[i] + k] == tmp1[sa[i - 1] + k])
                     ? tmp
                     : ++tmp;
    if (tmp == n) break;
    m = tmp;
  }
}
void MakeHeightArray() {
  int k = 0;
  for (int i = 1; i <= n; ++i) Rank[sa[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (Rank[i] == 1) continue;
    if (k) --k;
    int j = sa[Rank[i] - 1];
    while (j + k <= n && i + k <= n && a[i + k] == a[j + k]) ++k;
    height[Rank[i]] = k;
  }
}
int query_st(int l, int r) {
  if (l > r) return n;
  int lgs = lg[r - l + 1];
  return min(st[l][lgs], st[r - (1 << lgs) + 1][lgs]);
}
int query_l(int p, int q) {
  int l = 1, r = p, ans = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (query_st(mid + 1, p) >= q)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return ans;
}
int query_r(int p, int q) {
  int l = p, r = n, ans = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (query_st(p + 1, mid) >= q)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
void modify(int l, int r, int x, int now, int val) {
  if (l == r) {
    maxn[now] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    modify(l, mid, x, (now << 1), val);
  else
    modify(mid + 1, r, x, ((now << 1) | 1), val);
  maxn[now] = max(maxn[(now << 1)], maxn[((now << 1) | 1)]);
}
int query(int l, int r, int x, int y, int now) {
  if (l >= x && r <= y) return maxn[now];
  int mid = (l + r) >> 1;
  int ans = -10086001;
  if (x <= mid) ans = max(ans, query(l, mid, x, y, (now << 1)));
  if (mid + 1 <= y) ans = max(ans, query(mid + 1, r, x, y, ((now << 1) | 1)));
  return ans;
}
bool check(int x, int y) {
  int l = query_l(x, y), r = query_r(x, y);
  return query(1, n, l, r, 1) < y;
}
int main() {
  scanf("%d", &n);
  if (n == 1) return puts("1") & 0;
  scanf("%s", a + 1);
  MakeSuffixArray();
  MakeHeightArray();
  for (int i = 1; i <= n; ++i) st[i][0] = height[i];
  for (int j = 1; j <= 20; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  lg[1] = 0;
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  dp[n] = 1;
  int pointer = n, ans = 0;
  for (int i = n - 1; i; --i) {
    while (check(Rank[i], pointer - i) && check(Rank[i + 1], pointer - i) &&
           i < pointer)
      --pointer, modify(1, n, Rank[pointer + 1], 1, dp[pointer + 1]);
    ans = max(ans, dp[i] = pointer - i + 1);
  }
  printf("%d", ans);
  return 0;
}
