2, lower bound problem is always tricker..
we need adversary argument.

just consider this game, i play with adv.
in each round, i pick a element (i,j) from the matrix
then adv chooses to cover
either all elements (i',j') i'<=i and j'<=j
or all elements (i',j') i'>=i and j'>=j
How many step do i need to cover the whole n*n matrix.

this game is essentially equivalent to the problem, where I pick an element
and know which part of the matrix we don't need to consider any more.

To prove the game needs n round,
I just use a cleaner argument by Wu Jinyue @ mitbbs

"
my method is to consider the cells on the minor diagonal
if i compare x with a cell in the upper-left triangle,
adv answers x > that cell
if i compare x with a cell in the lower-right triangle,
adv answers x < that cell
if i compare x with a cell rightly on that diagonal
adv answers arbitrarily

in each round, at most one cell on the diagonal can be removed (no need to
be considered any more)
therefore, i need to ask at least n times.
"