Question 22
In a sequence $a_1, a_2, \dots, a_{1000}$ consisting of $1000$ distinct numbers, a pair $(a_i, a_j)$ with $i \lt j$ is called *ascending* if $a_i \lt a_j$ and *descending* if $a_i \gt a_j$. Determine the largest positive integer $k$ with the property that every sequence of $1000$ distinct numbers has at least $k$ non-overlapping ascending pairs or at least $k$ non-overlapping descending pairs.