Moving Through an Array

You are given an n × n array. Starting from cell (1, 1), you need to move to cell (n, n). Each move may go only to one of the four adjacent cells: up, down, left, or right.

For any path, consider all values written in the cells on that path, including the start and destination. Let the path's range be the difference between the maximum and minimum of those values. Find the smallest possible range among all valid paths.

The first line contains an integer n (2 ≤ n ≤ 100). Each of the next n lines contains n integers describing the array. Every value is an integer between 0 and 200, inclusive.

Output the minimum possible value of maximum - minimum over all valid paths.