Farmer John's Tractor

Farmer John has a hilly field represented as an \(N \times N\) grid of non-negative integer elevations. A tractor that is capable of moving between adjacent cells (north, east, south, or west) provided that the absolute difference in elevation between the two cells is no more than \(D\) costs exactly \(D\) monetary units.

FJ wants to purchase a tractor with the smallest possible \(D\) such that, starting from some cell, he can drive the tractor to visit at least \(\lceil \frac{N^2}{2} \rceil\) cells. Your task is to help him compute this minimum cost.

Note: Two cells are adjacent if they share a side. The number \(\lceil x \rceil\) denotes the smallest integer greater than or equal to \(x\).

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 500\)). Each of the next \(N\) lines contains \(N\) space-separated non-negative integers representing the grid elevations.

outputFormat

Output a single integer: the minimum \(D\) required such that there exists a starting cell from which the tractor can visit at least \(\lceil \frac{N^2}{2} \rceil\) cells.

sample

3
1 2 3
4 5 6
7 8 9

3