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 <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P) {
  in >> P.first >> P.second;
  return in;
}
template <class T1, class T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &P) {
  out << "(" << P.first << ", " << P.second << ")";
  return out;
}
template <class T>
istream &operator>>(istream &in, vector<T> &arr) {
  for (auto &x : arr) in >> x;
  return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &arr) {
  for (auto &x : arr) out << x << ' ';
  cout << "\n";
  return out;
}
template <class T>
istream &operator>>(istream &in, deque<T> &arr) {
  for (auto &x : arr) in >> x;
  return in;
}
template <class T>
ostream &operator<<(ostream &out, const deque<T> &arr) {
  for (auto &x : arr) out << x << ' ';
  cout << "\n";
  return out;
}
const int N = 500005;
namespace RMQ {
int rmq[22][N], jump[22][N];
void build(vector<int> v) {
  int n = v.size();
  for (int i = 0; i < n; i++) {
    rmq[0][i] = v[i];
    jump[0][i] = min(i + 1, n - 1);
  }
  for (int j = 1; j < 22; j++) {
    for (int i = 0; i < n; i++) jump[j][i] = jump[j - 1][jump[j - 1][i]];
  }
  for (int j = 1; j < 22; j++)
    for (int i = 0; i < n; i++) {
      rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][jump[j - 1][i]]);
    }
}
int query(int l, int r) {
  int sz = r - l + 1;
  int pot = 31 - __builtin_clz(sz);
  return min(rmq[pot][l], rmq[pot][r - (1 << pot) + 1]);
}
};  // namespace RMQ
class segment_tree {
 public:
  void init(int n) {
    st.clear();
    st.assign(4 * (n + 1), -1);
  }
  void update(int x, int v, int l, int r, int curr) {
    int mid = (l + r) / 2;
    if (l == r) {
      st[curr] = max(v, st[curr]);
      return;
    }
    if (x <= mid)
      update(x, v, l, mid, 2 * curr);
    else if (x > mid)
      update(x, v, mid + 1, r, 2 * curr + 1);
    return void(st[curr] = max(st[2 * curr], st[2 * curr + 1]));
  }
  int query(int x, int y, int l, int r, int curr) {
    int mid = (l + r) / 2;
    if (l == x && r == y) {
      return st[curr];
    }
    if (y <= mid)
      return query(x, y, l, mid, 2 * curr);
    else if (x > mid)
      return query(x, y, mid + 1, r, 2 * curr + 1);
    return max(query(x, mid, l, mid, 2 * curr),
               query(mid + 1, y, mid + 1, r, 2 * curr + 1));
  }

 private:
  vector<int> st;
};
namespace SA {
vector<int> buildSA(string s) {
  int n = (int)s.size();
  vector<int> ids(n), pos(n);
  vector<pair<int, int> > pairs(n);
  for (int i = 0; i < n; i++) {
    ids[i] = i;
    pairs[i] = pair<int, int>(s[i], -1);
  }
  sort(ids.begin(), ids.end(),
       [&](int a, int b) -> bool { return pairs[a] < pairs[b]; });
  int on = 0;
  for (int i = 0; i < n; i++) {
    if (i && pairs[ids[i - 1]] != pairs[ids[i]]) on++;
    pos[ids[i]] = on;
  }
  for (int offset = 1; offset < n; offset <<= 1) {
    for (int i = 0; i < n; i++) {
      pairs[i].first = pos[i];
      if (i + offset < n) {
        pairs[i].second = pos[i + offset];
      } else {
        pairs[i].second = -1;
      }
    }
    sort(ids.begin(), ids.end(),
         [&](int a, int b) -> bool { return pairs[a] < pairs[b]; });
    int on = 0;
    for (int i = 0; i < n; i++) {
      if (i && pairs[ids[i - 1]] != pairs[ids[i]]) on++;
      pos[ids[i]] = on;
    }
  }
  return ids;
}
vector<int> buildLCP(string s, vector<int> sa) {
  int n = (int)s.size();
  vector<int> pos(n), lcp(n, 0);
  for (int i = 0; i < n; i++) {
    pos[sa[i]] = i;
  }
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (pos[i] + 1 == n) {
      k = 0;
      continue;
    }
    int j = sa[pos[i] + 1];
    while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
    lcp[pos[i]] = k;
    k = max(k - 1, 0);
  }
  return lcp;
}
};  // namespace SA
int n, dp[N];
string s;
array<vector<int>, 2> sa;
vector<int> lcp;
int bsearchup(int x, int v) {
  int l = x + 1, r = n - 1;
  int ansj = x;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (RMQ::query(x, mid - 1) >= v) {
      ansj = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return ansj;
}
int bsearchdown(int x, int v) {
  int l = 0, r = x - 1;
  int ansj = x;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (RMQ::query(mid, x - 1) >= v) {
      ansj = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return ansj;
}
int32_t main() {
  cin >> n >> s;
  n = s.size();
  sa[0] = SA::buildSA(s);
  lcp = SA::buildLCP(s, sa[0]);
  sa[1] = sa[0];
  for (int i = 0; i < n; i++) {
    sa[1][sa[0][i]] = i;
  }
  RMQ::build(lcp);
  dp[n - 1] = 1;
  segment_tree st;
  st.init(n + 1);
  if (n != 1) dp[n - 2] = 1;
  int j = n - 1;
  int ans = 1;
  for (int i = n - 3; i >= 0; i--) {
    dp[i] = dp[i + 1];
    while (i + dp[i] < j) {
      st.update(sa[1][j], dp[j], 0, n - 1, 1);
      j--;
    }
    pair<int, int> tiraL = {bsearchdown(sa[1][i], dp[i]),
                            bsearchup(sa[1][i], dp[i])};
    pair<int, int> tiraF = {bsearchdown(sa[1][i + 1], dp[i]),
                            bsearchup(sa[1][i + 1], dp[i])};
    if (max(st.query(tiraF.first, tiraF.second, 0, n - 1, 1),
            st.query(tiraL.first, tiraL.second, 0, n - 1, 1)) >= dp[i]) {
      dp[i]++;
    } else {
      for (int k = dp[i]; k >= 1; k--) {
        while (i + dp[i] <= j) {
          st.update(sa[1][j], dp[j], 0, n - 1, 1);
          j--;
        }
        pair<int, int> aL = {bsearchdown(sa[1][i], k - 1),
                             bsearchup(sa[1][i], k - 1)};
        pair<int, int> aF = {bsearchdown(sa[1][i + 1], k - 1),
                             bsearchup(sa[1][i + 1], k - 1)};
        if (max(st.query(aF.first, aF.second, 0, n - 1, 1),
                st.query(aL.first, aL.second, 0, n - 1, 1)) >= k - 1) {
          break;
        } else {
          dp[i]--;
        }
      }
    }
    ans = max(ans, dp[i]);
  }
  cout << ans << endl;
}
