← 返回题目列表

Codeforces · 1063/F

F. 弦乐之旅

中文机器翻译题面 查看原题

我们将字符串序列 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}。