린던 분해

문자열 $X = X _ 0 X _ 1 X _ 2 \cdots$에 대해, 그 부분 문자열 $X _ a X _ {a+1} \cdots X _ {b-1}$을 $X[a,b)$로 나타낸다.

길이가 $N$인 문자열 $S = S _ 0 S _ 1 S _ 2 \cdots S _ {N-1}$이 주어진다. $S[a _ 0 , a _ 1) , S[a _ 1 , a _ 2) , \ldots , S[a _ {k-1} , a _ k)$이 $S$의 Lyndon Factorization이 되도록 정수 배열 $0 = a _ 0 \lt a _ 1 \lt a _ 2 \lt \ldots \lt a _ k = N$을 구한다.

제약 조건

• $1 \leq N \leq 500000$
• $S$의 각 문자는 영문 소문자이다.

$S$

$a _ 0$ $a _ 1$ $a _ 2$ $\cdots$ $a _ k$