IMC 2001 Problem 1

Let $n$ be a positive integer. Consider an $n\times n$ matrix with entries $1,2,...,n^2$ written in order, starting at the top left and moving along each row in turn left-to-right. (e.g. for $n = 3$ we get $\left[\begin{array}{ccc}1 & 2 & 3 4 & 5 & 6 7 & 8 & 9\end{array}\right]$ ) We choose $n$ entries of the matrix such that exactly one entry is chosen in each row and each column. What are the possible values of the sum of the selected entries?