We induct on $n$. Clearly, $n = 1$ works. So assume that the statement holds for $n = m$. Let $a_1,a_2,\ldots, a_{2m+2}$ be a sequence of integers. Suppose some number appears $m + 1$ times. Then we let all $b_i$'s be the indices corresponding to those numbers and let the $c_i$'s be all the other indices. This construction clearly works. Now, suppose each number in $\{a_i\}$ only appear at most $m$ times. Then let $k$ be the smallest index such that $a_k \neq a_1$. So $a_1 = a_2 = \ldots = a_{k - 1}$. Consider the sequence $a_2, a_3,\ldots, a_{k-1}, a_{k+1}, a_{k+2}, \ldots a_{2m + 2}$ with $2m$ terms. By induction, there exist $b_2, b_3, ..., b_{m+1}$ and $c_2, c_3, ..., c_{m+1}$ that satisfy the condition. Let $b_1 = 1$ and $c_1 = k$. Since $a_{b_1} \neq a_{c_1}$, this satisfies the condition. So the statement holds for $n = m + 1$, and the induction is complete.