Construct a Sequence

Set $A_i=2i-1$. These values are distinct and lie between $1$ and $2N$.

A contiguous subsequence of length $k$ starting with $2l-1$ has sum $k(2l+k-2)$, so its average is always an integer.

The time complexity is $O(N)$.

Solution written by GPT5