IMC 2001 · Problem 1

Let $n$ be a positive integer. Consider an $n \times n$ matrix with entries $1, 2, \dots, n^2$ written in order starting top left and moving along each row in turn left–to–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?