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 = 5e5 + 5, lg = 20;
int n;
int rmq[maxn][lg + 5], rmq2[maxn][lg + 5];
int seg[maxn * 4], ind[maxn], dp[maxn];
long long base = 761, mod = 1e9 + 7;
long long hsh[maxn], pw[maxn], lc[maxn], sf[maxn];
vector<int> vec[maxn], sec[maxn];
int rnk[maxn];
char s[maxn];
inline long long get_hash(int l, int r) {
  return (hsh[r] - hsh[l] * pw[r - l] % mod + mod) % mod;
}
inline int lcp(int i, int j) {
  int l = 0, r = n - max(i, j) + 1;
  while (l + 1 < r) {
    int mid = (l + r) / 2;
    if (get_hash(i, i + mid) == get_hash(j, j + mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  return l;
}
vector<pair<pair<int, int>, int>> radix_sort(
    vector<pair<pair<int, int>, int>> v) {
  int k = max(n, 30);
  for (int i = 0; i <= k; i++) {
    vec[i].clear();
    sec[i].clear();
  }
  for (int i = 0; i < n; i++) {
    vec[v[i].first.second + 1].push_back(i);
  }
  for (int i = 0; i <= k; i++) {
    for (int u : vec[i]) {
      sec[v[u].first.first + 1].push_back(u);
    }
  }
  vector<pair<pair<int, int>, int>> ne;
  int p = 0;
  for (int i = 0; i <= k; i++) {
    for (int u : sec[i]) {
      sf[p] = v[u].second;
      ne.push_back(v[u]);
      p++;
    }
  }
  return ne;
}
void find_sf() {
  for (int i = 0; i < n; i++) {
    rnk[i] = s[i] - 'a';
  }
  for (int t = 0; t < 20; t++) {
    vector<pair<pair<int, int>, int>> vec;
    for (int i = 0; i < n; i++) {
      if (i + (1 << t) >= n) {
        vec.push_back({{rnk[i], -1}, i});
      } else {
        vec.push_back({{rnk[i], rnk[i + (1 << t)]}, i});
      }
    }
    vec = radix_sort(vec);
    rnk[vec[0].second] = 0;
    for (int i = 1; i < n; i++) {
      rnk[vec[i].second] =
          rnk[vec[i - 1].second] + (vec[i].first != vec[i - 1].first);
    }
  }
}
inline void suffix_array() {
  pw[0] = 1;
  for (int i = 0; i < n; i++) {
    hsh[i + 1] = (hsh[i] * base % mod + s[i]) % mod;
    pw[i + 1] = pw[i] * base % mod;
  }
  find_sf();
  for (int i = 0; i < n; i++) {
    ind[sf[i]] = i;
  }
  for (int i = 0; i < n - 1; i++) {
    lc[i + 1] = lcp(sf[i], sf[i + 1]);
  }
  for (int i = 0; i < n; i++) {
    rmq[i][0] = lc[i];
    for (int j = 1; j < lg; j++) {
      rmq[i][j] = min(rmq[i][j - 1], rmq[max(0, i - (1 << (j - 1)))][j - 1]);
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    rmq2[i][0] = lc[i + 1];
    for (int j = 1; j < lg; j++) {
      rmq2[i][j] =
          min(rmq2[i][j - 1], rmq2[min(n - 1, i + (1 << (j - 1)))][j - 1]);
    }
  }
}
inline int find_l(int ind, int val) {
  for (int i = lg - 1; (ind >= 0) && i >= 0; i--) {
    if (rmq[ind][i] >= val && ind - (1 << i) >= 0) {
      ind -= (1 << i);
    }
  }
  return ind;
}
inline int find_r(int ind, int val) {
  for (int i = lg - 2; (ind < n) && i >= 0; i--) {
    if (rmq2[ind][i] >= val && ind + (1 << i) < n) {
      ind += (1 << i);
    }
  }
  return ind;
}
inline void add(int l, int r, int ind, int val, int x) {
  if (l + 1 >= r) {
    seg[x] += val;
    return;
  }
  int mid = (l + r) / 2;
  if (ind < mid) {
    add(l, mid, ind, val, x * 2);
  } else {
    add(mid, r, ind, val, x * 2 + 1);
  }
  seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
}
inline int get(int l, int r, int L, int R, int x) {
  if (l >= R || r <= L) {
    return 0;
  }
  if (l >= L && r <= R) {
    return seg[x];
  }
  int mid = (l + r) / 2;
  return max(get(l, mid, L, R, x * 2), get(mid, r, L, R, x * 2 + 1));
}
inline bool check(int i, int val) {
  int l1 = find_l(ind[i], val - 1);
  int r1 = find_r(ind[i], val - 1) + 1;
  int l2 = find_l(ind[i + 1], val - 1);
  int r2 = find_r(ind[i + 1], val - 1) + 1;
  return (get(0, n, l1, r1, 1) >= val - 1 || get(0, n, l2, r2, 1) >= val - 1);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  scanf("%d %s", &n, &s);
  suffix_array();
  int p = n - 1;
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    int y = dp[i + 1] + 1;
    while (p > 0 && !check(i, y)) {
      add(0, n, ind[p], dp[p], 1);
      y--;
      p--;
    }
    dp[i] = y;
    ans = max(ans, dp[i]);
  }
  printf("%d", ans);
  return 0;
}
