TSTST 2022 Problem 9

Let $k>1$ be a fixed positive integer. Prove that if $n$ is a sufficiently large positive integer, there exists a sequence of integers with the following properties: - Each element of the sequence is between 1 and $n$, inclusive. - For any two different contiguous subsequences of the sequence with length between 2 and $k$ inclusive, the multisets of values in those two subsequences is not the same. - The sequence has length at least $0.499 n^{2}$.