P9770 [HUSTFC 2023] Reverse KMP

Walk Alone is a master of strings, but he has become bored with traditional string algorithms such as the KMP algorithm, so recently he has been thinking about a reversed version of KMP. Here is the problem he proposed: You are given an integer sequence $a$ of length $n$. For any integer $i\ (1\le i\le n)$, it satisfies $0\le a_i

The first line contains an integer $n\ (1\le n\le 2\cdot 10^5)$, which denotes the length of sequence $a$. The second line contains $n$ integers, where the $i$-th integer is defined as $a_i\ (0\le a_i

Output $n$ integers separated by spaces, where the $i$-th integer is defined as $s_i$. If there are multiple valid answers, output the lexicographically smallest one.

Translated by ChatGPT 5