Prefixuffix

이 문제에서는 영어 소문자로 이루어진 문자열만 다룹니다. 문자열의 앞쪽 일부를 접두사, 뒤쪽 일부를 접미사라고 합니다. 특히 빈 문자열은 모든 문자열의 접두사이면서 접미사입니다.

두 문자열이 순환 동치(cyclically equivalent)라는 것은, 한 문자열의 어떤 접미사를 끝에서 떼어 맨 앞으로 옮기면 다른 문자열이 되는 경우를 말합니다. 예를 들어 ababba와 abbaab는 순환 동치이지만, ababba와 ababab는 순환 동치가 아닙니다. 모든 문자열은 자기 자신과 순환 동치입니다.

길이가 $n$인 문자열 $t$가 주어집니다. 다음 세 조건을 모두 만족하는, 길이가 같은 접두사 $p$와 접미사 $s$를 찾으세요.

• $p$와 $s$가 순환 동치이다.
• 공통 길이가 $\frac{n}{2}$ 이하이다. (즉, $t$ 안에서 $p$와 $s$가 서로 겹치지 않는다.)
• 공통 길이가 최대이다.

첫째 줄에 문자열 $t$의 길이 $n$이 주어집니다. ($1 \le n \le 10^6$)

둘째 줄에 영어 소문자로 이루어진 문자열 $t$가 주어집니다.

위 조건을 만족하는 접두사 $p$와 접미사 $s$의 최대 공통 길이를 정수 하나로 출력합니다.