Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could be its slogans, while strings "e" and "hornss" can not.

Sometimes the company performs rebranding and changes its slogan. Slogan A is considered to be cooler than slogan B if B appears in A as a substring at least twice (this occurrences are allowed to overlap). For example, slogan A =  "abacaba" is cooler than slogan B =  "ba", slogan A =  "abcbcbe" is cooler than slogan B =  "bcb", but slogan A =  "aaaaaa" is not cooler than slogan B =  "aba".

You are given the company name w and your task is to help Bomboslav determine the length of the longest sequence of slogans s1, s2, ..., sk, such that any slogan in the sequence is cooler than the previous one.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the company name that asks Bomboslav to help. The second line contains the string w of length n, that consists of lowercase English letters.

Output

Print a single integer — the maximum possible length of the sequence of slogans of the company named w, such that any slogan in the sequence (except the first one) is cooler than the previous

Examples

Input

3
abc


Output

1


Input

5
ddddd


Output

5


Input

11
abracadabra


Output

3
#include <bits/stdc++.h>
const int MAX_N = 2e5 + 10, SIGMA = 26;
int N, ans;
char S[MAX_N];
struct SegTree {
  int l, r, m;
  SegTree *cl, *cr;
  SegTree(int l, int r)
      : l(l), r(r), m((l + r) / 2), cl(nullptr), cr(nullptr) {}
};
SegTree *touch(int l, int r, int x) {
  SegTree *res = new SegTree(l, r);
  if (l != r) {
    if (x <= res->m)
      res->cl = touch(l, res->m, x);
    else
      res->cr = touch(res->m + 1, r, x);
  }
  return res;
}
SegTree *merge(SegTree *a, SegTree *b) {
  if (!a) return b;
  if (!b) return a;
  SegTree *res = new SegTree(a->l, a->r);
  res->cl = merge(a->cl, b->cl);
  res->cr = merge(a->cr, b->cr);
  return res;
}
int last_before(SegTree *t, int x) {
  if (!t || t->l > x) return -1;
  if (t->l == t->r) return t->l;
  int res = last_before(t->cr, x);
  return res == -1 ? last_before(t->cl, x) : res;
}
int first_after(SegTree *t, int x) {
  if (!t || t->r < x) return -1;
  if (t->l == t->r) return t->l;
  int res = first_after(t->cl, x);
  return res == -1 ? first_after(t->cr, x) : res;
}
struct SAM {
  struct Node {
    int len, right, f, flen;
    Node *trans[SIGMA], *fail;
    SegTree *seg, *fseg;
    Node(SAM *sam, int len, int right)
        : len(len),
          right(right),
          f(0),
          flen(0),
          fail(nullptr),
          seg(nullptr),
          fseg(nullptr) {
      sam->nodes.push_back(this);
      std::fill_n(trans, SIGMA, nullptr);
    }
  } * empty, *last;
  std::vector<Node *> nodes;
  SAM() { last = empty = new Node(this, 0, 0); }
  void extend(int ch) {
    Node *u = new Node(this, last->len + 1, last->len + 1), *v = last;
    for (; v && !v->trans[ch]; v = v->fail) v->trans[ch] = u;
    if (!v)
      u->fail = empty;
    else {
      Node *q = v->trans[ch];
      if (q->len == v->len + 1)
        u->fail = q;
      else {
        Node *p = new Node(this, v->len + 1, 0);
        p->fail = q->fail;
        q->fail = u->fail = p;
        std::copy_n(q->trans, SIGMA, p->trans);
        for (; v && v->trans[ch] == q; v = v->fail) v->trans[ch] = p;
      }
    }
    last = u;
  }
  void solve() {
    sort(nodes.begin(), nodes.end(),
         [](Node *a, Node *b) { return a->len < b->len; });
    for (auto i = nodes.rbegin(); i != nodes.rend(); i++) {
      Node *node = *i;
      if (node->right) node->seg = merge(node->seg, touch(1, N, node->right));
      if (node->fail) node->fail->seg = merge(node->seg, node->fail->seg);
    }
    for (Node *node : nodes) {
      if (node == empty) continue;
      if (node->fail == empty) {
        node->f = 1;
        node->fseg = node->seg;
        node->flen = node->len;
      } else {
        int p = first_after(node->seg, 1);
        int pf = last_before(node->fail->fseg, p - 1);
        if (pf - node->fail->flen + 1 >= p - node->len + 1) {
          node->f = node->fail->f + 1;
          node->fseg = node->seg;
          node->flen = node->len;
        } else {
          node->f = node->fail->f;
          node->fseg = node->fail->fseg;
          node->flen = node->fail->flen;
        }
      }
      ans = std::max(ans, node->f);
    }
  }
} sam;
int main() {
  std::scanf("%d", &N);
  std::scanf("%s", S + 1);
  for (int i = 1; i <= N; i++) sam.extend(S[i] - 'a');
  sam.solve();
  std::printf("%d\n", ans);
}
