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;
int n, tot, ans, rk[2000000], sa[2000000], dp[2000000], w[2000000],
    lcp[2000000][20];
bool df[2000000];
char s[2000000];
vector<int> v1[2000000], v2[2000000];
void f(int x, int y, int z, int L, int R) {
  if (L == R) {
    w[x] = z;
    return;
  }
  int m = (L + R) / 2;
  if (y <= m)
    f(x * 2, y, z, L, m);
  else
    f(x * 2 + 1, y, z, m + 1, R);
  w[x] = max(w[x * 2], w[x * 2 + 1]);
}
int q(int x, int l, int r, int L, int R) {
  if (l == L && r == R) return w[x];
  int m = (L + R) / 2;
  if (r <= m) return q(x * 2, l, r, L, m);
  if (l > m) return q(x * 2 + 1, l, r, m + 1, R);
  return max(q(x * 2, l, m, L, m), q(x * 2 + 1, m + 1, r, m + 1, R));
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = (1); i <= (n); i++) v1[s[i] - 'a' + 1].push_back(i);
  for (int i = (1); i <= (26); i++)
    if (!v1[i].empty()) {
      tot++;
      for (auto j : v1[i]) rk[j] = tot;
    }
  for (int i = (0); i <= (18); i++) {
    tot = 0;
    for (int j = (0); j <= (n); j++) {
      v1[j].clear();
      v2[j].clear();
      df[j] = 0;
    }
    for (int j = (1); j <= (n); j++) v1[rk[j + (1 << i)]].push_back(j);
    for (int j = (0); j <= (n); j++)
      for (auto k : v1[j]) {
        if (v2[rk[k]].empty() ||
            rk[*(--v2[rk[k]].end()) + (1 << i)] != rk[k + (1 << i)])
          df[k] = 1;
        v2[rk[k]].push_back(k);
      }
    for (int j = (0); j <= (n); j++)
      for (auto k : v2[j]) {
        if (df[k]) tot++;
        rk[k] = tot;
      }
  }
  for (int i = (1); i <= (n); i++) sa[rk[i]] = i;
  for (int i = (1); i <= (n); i++) {
    lcp[rk[i]][0] = max(lcp[rk[i - 1]][0] - 1, 0);
    while (s[i + lcp[rk[i]][0]] == s[sa[rk[i] - 1] + lcp[rk[i]][0]])
      lcp[rk[i]][0]++;
  }
  for (int j = (1); j <= (19); j++)
    for (int i = (1); i <= (n); i++)
      lcp[i][j] = min(lcp[i][j - 1], lcp[i + (1 << (j - 1))][j - 1]);
  for (int i = (n); i >= (1); i--) {
    dp[i] = dp[i + 1] + 1;
    while (dp[i] > 1) {
      int l = rk[i], r = rk[i] + 1;
      for (int j = (19); j >= (0); j--) {
        if (l >= 1 << j && lcp[l + 1 - (1 << j)][j] >= dp[i] - 1) l -= 1 << j;
        if (lcp[r][j] >= dp[i] - 1) r += 1 << j;
      }
      if (q(1, l, r - 1, 1, n) + 1 >= dp[i]) break;
      l = rk[i + 1];
      r = rk[i + 1] + 1;
      for (int j = (19); j >= (0); j--) {
        if (l >= 1 << j && lcp[l + 1 - (1 << j)][j] >= dp[i] - 1) l -= 1 << j;
        if (lcp[r][j] >= dp[i] - 1) r += 1 << j;
      }
      if (q(1, l, r - 1, 1, n) + 1 >= dp[i]) break;
      dp[i]--;
      f(1, rk[i + dp[i]], dp[i + dp[i]], 1, n);
    }
    if (dp[i] > ans) ans = dp[i];
  }
  printf("%d\n", ans);
}
