Bomboslav 成立了一家品牌代理机构,现在帮助公司创建新的徽标和广告口号。针对这个问题,公司的口号应该是公司名称的非空子串。例如,如果公司名称是“hornsandhoofs”,则子字符串“sand”和“hor”可以是其口号,而字符串“e”和“hornss”则不能。
有时,公司会进行品牌重塑并更改其口号。如果B作为子串在A中出现至少两次(允许重叠),则认为口号A比口号B更酷。例如,口号 A =“abacaba”比口号 B =“ba”酷,口号 A =“abcbcbe”比口号 B =“bcb”酷,但口号 A =“aaaaaa”并不比口号 B =“aba”酷。
你的公司名称是 w,你的任务是帮助 Bomboslav 确定最长的口号序列 s1, s2, ..., sk 的长度,使得序列中的任何口号都比前一个更酷。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 请求 Bomboslav 提供帮助的公司名称的长度。第二行包含长度为n的字符串w,由小写英文字母组成。
输出
打印一个整数——名为w的公司的口号序列的最大可能长度,使得序列中的任何口号(除了第一个)都比前一个更酷
示例
输入 #1
3 abc
输出 #1
1
输入 #2
5 ddddd
输出 #2
5
输入 #3
11 abracadabra
输出 #3
3