(CH) Bear and Sorted Rows

Limak has a grid that consists of N rows and N columns. He randomly wrote all numbers 1 through N2 in the cells of the grid, one number in each cell. You can assume that each of (N2)! ways was equally likely. Limak asks you to rearrange the numbers in the grid, so that each row will be sorted either increasingly or decreasingly. Scoring Let (r, c) denote the cell at the intersection of the