Define a complexity of a set $a_1,a_2,\dots,$ consisting of 0 and 1 to be the smallest positive integer $k$ such that for some positive integers $\epsilon_1,\epsilon_2,\dots, \epsilon_k$ each number of the sequence $a_n$, $n>k$, has the same parity as $\epsilon_1 a_{n-1}+\epsilon_2 a_{n-2}+\dots+\epsilon_k a_{n-k}$. Sequence $a_1,a_2,\dots,$ has a complexity of $1000$. What is the complexity of sequence $1-a_1,1-a_2,\dots,$. Proposed by A. Kirichenko