MathNet 2014 Question 11

The numbers $1, 2, \dots, n^2$ are put in some order into the squares of a checkered $n \times n$ board, one number per square. Pete performs several moves according to the following rules. On the first move, he puts a token into some square. By any subsequent move, he may either put a new token into an arbitrary square, or to move a token horizontally or vertically from a square containing some number $a$ to any square containing a number greater than $a$. Every time a token is put onto a square, this square is marked; it is prohibited to put a token into a marked square.
Find the least number $k$ such that for every arrangement of the numbers, Pete can mark all the squares of the board using at most $k$ tokens.