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?

UPDATE: It appears the statement is false. The paper "On permutations containing no long arithmetic progressions," by Davis, Entringer, Graham, and Simmons [Acta Arithmetica 34 (1977)] exhibits a permutation of the positive integers that has no arithmetic progressions of length $5$. The range of this sequence has density $1/2$.