Szemerédi's theorem states that a strictly increasing sequence of positive integers $a_0, a_1, \ldots$ whose range has positive density contains arbitrarily long arithmetic progressions (as subsequences). I was wondering if the statement still holds when the sequence is not required to be strictly increasing (for any $k$, there is an $n$ such that an arithmetic progression can be found in $a_0,\ldots, a_n$). Perhaps there is some example where, even though the range is of positive density, the elements are shuffled in such a way that, for large enough $k$, no arithmetic progression of length $k$ can appear.

I tried to reduce the problem to the original theorem by waiting long enough in the sequence until a dense subset of $[-N,N]$ appears and then applying Erdős-Szekeres, but this does not seem to work because the length of the monotone subsequence will scale like $\delta \sqrt N$.

This seems like a problem that has been studied before, so would anyone be able to point me towards a reference?