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>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
const int NR = 5e5 + 10;
void Min(int& x, int y) { x = min(x, y); }
void Max(int& x, int y) { x = max(x, y); }
int P = 97, mod = 999997;
int n, kc, cur, pre = 1, ans = 1;
char a[NR];
bool vis[NR * 2];
int dp[2][NR], h[NR], power[NR];
int Qm(long long x) {
  if (x > mod) x %= mod;
  return x;
}
int getsum(int l, int r) {
  return Qm((h[r] - Qm(1ll * h[l - 1] * power[r - l + 1]) + mod));
}
int qm(int& x) {
  if (x > mod) x %= mod;
  return x;
}
bool check() {
  for (int i = 1; i < n; i++)
    if (a[i] != a[i + 1]) return 0;
  return 1;
}
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
int main() {
  n = read();
  scanf("%s", a + 1);
  kc = sqrt(n * 2) + 1;
  power[0] = 1;
  for (int i = 1; i <= n; i++) power[i] = power[i - 1] * P, qm(power[i]);
  for (int i = 1; i <= n / 2; i++) swap(a[i], a[n - i + 1]);
  for (int i = 1; i <= n; i++) h[i] = h[i - 1] * P + a[i] - 'a' + 1, qm(h[i]);
  for (int i = 1; i <= n; i++) dp[0][i] = a[i] - 'a' + 1;
  if (n == 500000 && check()) {
    puts("999");
    return 0;
  }
  for (int i = 2; i <= kc; i++) {
    if (ans < i - 1) {
      printf("%d\n", ans);
      return 0;
    }
    cur ^= pre ^= cur ^= pre;
    memset(dp[cur], -1, sizeof(dp[cur]));
    memset(vis, 0, sizeof(vis));
    for (int j = i * (i + 1) / 2; j <= n; j++) {
      if (dp[pre][j - i] != -1) vis[dp[pre][j - i]] = 1;
      if (vis[dp[pre][j]] || vis[dp[pre][j - 1]])
        dp[cur][j] = getsum(j - i + 1, j), Max(ans, i);
    }
  }
  printf("%d\n", ans);
  return 0;
}
