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;
template <typename T>
T rd() {
  T nmb = 0;
  int sgn = 0;
  char chr = getchar();
  while (!isdigit(chr)) {
    if (chr == '-') sgn = 1;
    chr = getchar();
  }
  while (isdigit(chr)) {
    nmb = (nmb << 3) + (nmb << 1) + chr - '0';
    chr = getchar();
  }
  return sgn ? -nmb : nmb;
}
template <typename T>
void wt(T nmb) {
  if (nmb > 9) wt(nmb / 10);
  putchar(nmb % 10 + '0');
}
template <typename T>
void cmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void cmin(T &x, T y) {
  x = x < y ? x : y;
}
void proc_status() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>())
       << endl;
}
const int N = 5e5 + 10, L = 1e6 + 10, K = 30;
int n;
char S[N];
int pos[N];
int lst = 1, cnt = 1;
int ch[L][K], mx[L], pre[L];
void insert(int c) {
  int np = ++cnt, p = lst;
  mx[np] = mx[p] + 1;
  lst = np;
  for (; p && !ch[p][c]; p = pre[p]) ch[p][c] = np;
  if (!p)
    pre[np] = 1;
  else {
    int q = ch[p][c];
    if (mx[q] == mx[p] + 1)
      pre[np] = q;
    else {
      int nq = ++cnt;
      memcpy(ch[nq], ch[q], sizeof ch[q]);
      mx[nq] = mx[p] + 1;
      pre[nq] = pre[q];
      pre[np] = pre[q] = nq;
      for (; p && ch[p][c] == q; p = pre[p]) ch[p][c] = nq;
    }
  }
}
vector<int> g[L];
int dfn[L], Cnt;
int siz[L];
void dfs(int x) {
  dfn[x] = ++Cnt;
  siz[x] = 1;
  for (int i = g[x].size() - 1; ~i; --i) {
    int k = g[x][i];
    dfs(k);
    siz[x] += siz[k];
  }
}
int dp[N];
int val[L << 2];
void change(int r, int x, int y, int k, int p) {
  if (x == y) {
    val[r] = p;
    return;
  }
  int m = (x + y) >> 1;
  if (k <= m)
    change(r << 1, x, m, k, p);
  else
    change(r << 1 | 1, m + 1, y, k, p);
  val[r] = max(val[r << 1], val[r << 1 | 1]);
}
int query(int r, int x, int y, int u, int v) {
  if (u <= x && y <= v) return val[r];
  int m = (x + y) >> 1;
  int res = 0;
  if (u <= m) res = query(r << 1, x, m, u, v);
  if (m < v) cmax(res, query(r << 1 | 1, m + 1, y, u, v));
  return res;
}
void Init() {
  n = rd<int>();
  scanf("%s", S + 1);
  reverse(S + 1, S + n + 1);
  for (int i = 1; i <= n; ++i) insert(S[i] - 'a' + 1), pos[i] = lst;
  for (int i = 2; i <= cnt; ++i) g[pre[i]].push_back(i);
  dfs(1);
  S[0] = 'a' - 1;
}
void Solve() {
  int p1 = 1, p2 = 1;
  for (int i = 1; i <= n; ++i) {
    int c1 = S[i - 1] - 'a' + 1, c2 = S[i] - 'a' + 1;
    while (p1 && !ch[p1][c1]) p1 = pre[p1];
    while (p2 && !ch[p2][c2]) p2 = pre[p2];
    p1 = p1 ? ch[p1][c1] : 1;
    p2 = p2 ? ch[p2][c2] : 1;
    dp[i] = dp[i - 1] + 1;
    while (dp[i] > 1) {
      while (p1 && mx[pre[p1]] >= dp[i] - 1) p1 = pre[p1];
      while (p2 && mx[pre[p2]] >= dp[i] - 1) p2 = pre[p2];
      if (dp[i] <= query(1, 1, cnt, dfn[p1], dfn[p1] + siz[p1] - 1) + 1) break;
      if (dp[i] <= query(1, 1, cnt, dfn[p2], dfn[p2] + siz[p2] - 1) + 1) break;
      change(1, 1, cnt, dfn[pos[i - dp[i] + 1]], dp[i - dp[i] + 1]);
      --dp[i];
    }
  }
  int Ans = 0;
  for (int i = 1; i <= n; ++i) cmax(Ans, dp[i]);
  printf("%d\n", Ans);
}
int main() {
  Init();
  Solve();
  return 0;
}
