Let $a_1, a_2, a_3, \ldots$ be an infinite sequence where for all positive integers $i$, $a_i$ is chosen to be a random positive integer between $1$ and $2016$, inclusive. Let $S$ be the set of all positive integers $k$ such that for all positive integers $j < k$, $a_j \neq a_k$. (So $1 \in S$; $2 \in S$ if and only if $a_1 \neq a_2$; $3 \in S$ if and only if $a_1 \neq a_3$ and $a_2 \neq a_3$; and so on.) In simplest form, let $\frac{p}{q}$ be the expected number of positive integers $m$ such that $m$ and $m+1$ are in $S$. Compute $pq$.

Let's think step by step and output the final answer within \boxed{}.
user