P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

Two sides of the same coin, sweetness and bitterness.

Before falling into a coma, Susan experienced $m$ days of memories. Starting from the first day, Susan has a base memory value $x$. The memory for the $i$-th day ($1 \le i \le m$) is $x + i - 1$. These $m$ days of memories are concatenated in order to form a sequence of length $m$. In her dreams, this memory sequence is repeated $k$ times in order. Afterward, to awaken Susan, Luvia intervenes in the dream, inserting foreign memories not belonging to Susan. The final result is a sequence $a_1, a_2, \ldots, a_n$ of length $n$. Given this sequence and $k$, Luvia wants to determine the maximum possible value of $m$ for every possible base memory $x$ where $1 \le x \le V$. If no valid memory sequence exists for a particular $x$, output $0$.

- The first line contains three integers $n$, $k$, $V$, as described. - The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing the final sequence.

Output one line containing $V$ integers, where the $i$-th integer represents the maximum possible $m$ when $x = i$.

**Sample Explanation #1** For $x = 2$ and $m = 3$, Susan's memory sequence is `2 3 4`. Repeating $k = 2$ times gives `2 3 4 2 3 4`. After inserting values between positions $1$ and $2$, $3$ and $4$, and $5$ and $6$, the sequence matches the original input. Similarly, sequences like `2`, `3`, `4`, `2 3`, and `3 4` are all valid. **Data Range** **This problem uses subtasks with bundled testing.** - Subtask 1 (13 pts): $n \le 100$. - Subtask 2 (21 pts): $n \le 3000$. - Subtask 3 (23 pts): $n \le 3 \times 10^4$. - Subtask 4 (25 pts): $n \le 5 \times 10^5$. - Subtask 5 (18 pts): No additional constraints. For all data: $1 \le k \le n \le 2 \times 10^6$, $1 \le a_i \le V \le n$. Translation by DeepSeek R1