Question 128
Let $n$ be a positive integer such that there exists a positive integer that is less than $\sqrt{n}$ and does not divide $n$. Let $(a_1, \dots, a_n)$ be an arbitrary permutation of $1, \dots, n$. Let $a_{i_1} \lt \dots \lt a_{i_k}$ be its maximal increasing subsequence and let $a_{j_1} \gt \dots \gt a_{j_l}$ be its maximal decreasing subsequence. Prove that tuples $(a_{i_1}, \dots, a_{i_k})$ and $(a_{j_1}, \dots, a_{j_l})$ altogether contain at least one number that does not divide $n$.