https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

It is just a direct application of Erdos-Szekeres Theorem. You have at least $\lceil \sqrt{n} \rceil$ numbers in increase order or in decrease order, so the minimum $k$ is at least $n- \lceil \sqrt{n} \rceil$. For an example, let $n=a^2+r$, with $0 < r \le 2a$ (note that $a=\lfloor \sqrt{n} \rfloor = \lceil \sqrt{n} \rceil -1$ and consider the numbers in the order $X_{a+1},X_a,...,X_1$, where: $$ X_{a+1} = a^2+1,..., a^2 +r; X_a=a(a-1)+1,...,a^2; X_(a-1)=a(a-2)+1,...,a(a-1);...;X_1=a(1-1)+1,...,a $$ If $a+2$ numbers remains in the end, satisfying the question, then they are in increasing order, since two of then are on the same $X_i$. However, there also two numbers on different $X_I,X_j$ as well, so they are in decreasing order, a contradiction. The example for $r=0$ is similar, because $X_{a+1}$ is empty and $\lfloor \sqrt{n} \rfloor = \lceil \sqrt{n} \rceil =a$. So, $k=n- \lceil \sqrt{n} \rceil$.

Davi Medeiros wrote: However, there also two numbers on different $X_I,X_j$ as well, so they are in decreasing order, a contradiction. In case $r >a+1$ if we remain the set $X_{a+1}$, $r $ numbers will be an increasing order. I think there is a mistake. Who knows correct solution?

Who can kill this problem??????

Just split the integers $1,2,3..,n$ into $\lceil \sqrt n \rceil$consecutive chunks each of size at most $\lceil\sqrt n\rceil$ ( so that the size of all chunks differ by at most $1$) and order each chunk internally in decreasing order .