DE-MO 2018 Problem 3

Given a positive integer $n$ , Susann fills a square of $n \times n$ boxes. In each box she inscribes an integer, taking care that each row and each column contains distinct numbers. After this an imp appears and destroys some of the boxes. Show that Susann can choose some of the remaining boxes and colour them red, satisfying the following two conditions:

1. There are no two red boxes in the same column or in the same row.
2. For each box which is neither destroyed nor coloured, there is a red box with a larger number in the same row or a red box with a smaller number in the same column. Proposed by Christian Reiher