我们将字符串序列 t1, ..., tk 称为长度为 k 的旅程,如果对于每个 i > 1 ti 是 ti - 1 的子串,并且 ti 的长度严格小于 ti - 1 的长度。例如,{ab, b} 是一个旅程,但 {ab, c} 和 {a, a} 不是。
将字符串 s 上的旅程定义为旅程 t1, ..., tk,这样其所有部分都可以嵌套在 s 内,从而存在一系列字符串 u1, ..., uk + 1 (每个字符串都可以为空)且 s = u1 t1 u2 t2... uk tk uk + 1。例如,{ab, b} 是字符串 abb 上的旅程,但不是在 bab 上,因为旅程字符串 ti 应该从左到右出现。
绳子上的旅程长度是其中绳子的数量。确定给定字符串 s 上旅程的最大可能长度。
输入
第一行包含一个整数 n (1 ≤ n ≤ 500 000) — 字符串 s 的长度。
第二行包含字符串 s 本身,由 n 个小写拉丁字母组成。
输出
打印一个数字——s 上字符串行程的最大可能长度。
示例
输入 #1
7 abcdbcc
输出 #1
3
输入 #2
4 bbcb
输出 #2
2
注意
在第一个样本中,最大长度的字符串旅程为{abcd, bc, c}。
在第二个示例中,合适的旅程之一是 {bb, b}。