Given list of numbers find for each number in the list the next distinct number
Here is pseudocode for an algorithm which outputs the entire answer array $a_1,\ldots,a_n$:

Set $\mathit{first} \gets 1$ (first index in the current run)
Set $\mathit{curr} \gets 1$ (index of the current element being scanned)
While $\mathit{curr} &lt; n$:
   Set $\mathit{curr} \gets \mathit{curr} + 1$
   If $l_{\mathit{curr}} \neq l_{\mathit{first}}$:
     Set $a_{\mathit{first}},\ldots,a_{\mathit{curr}-1} \gets l_{\mathit{curr}}$
     Set $\mathit{first} \gets \mathit{curr}$
   End If
End While
Set $a_{first},\ldots,a_n \gets \bot$ (no different element to the right)

This algorithm uses linear time and $O(1)$ auxiliary space.