Costly Array

Consider the $[l, r]$ that is longest, then we will at least need $r-l+1$ distinct values. let this value be $m$, then we can just put the numbers $1, \cdots, m$ and keep repeating these (i.e. put the number $((i-1) \mod m) + 1$ at index $i$). Since all conditions are of length smaller or equal to $m$, this is a valid solution and the optimal solution.