OIM

Los números $1,2,3, \cdots , n^2$ se colocan en las casillas de una cuadrícula de $n \times n$, en algún orden, un número por casilla. Una ficha se encuentra inicialmente en la casilla con el número $n^2$. En cada paso, la ficha puede avanzar a cualquiera de las casillas que comparten un lado con la casilla donde se encuentra. Primero, la ficha viaja a la casilla con el número $1$, y para ello toma uno de los caminos más cortos (con menos pasos) entre la casilla con el número $n^2$ y la casilla con el número $1$. Desde la casilla con el número $1$ viaja a la casilla con el número $2$, desde allí a la casilla con el número $3$, y así sucesivamente, hasta que regresa a la casilla inicial, tomando en cada uno de los viajes el camino más corto. El recorrido completo le toma a la ficha $N$ pasos. Determine el menor y mayor valor posible de $N$.