#include <bits/stdc++.h>
using namespace std;

int n;
bool ans;
int grid[505][505];
bool visited[505][505];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int maxi = 0;
bool valid(int x, int y, int m, int a, int b) {
    return x < n && x >= 0 && y < n && y >= 0 && !visited[x][y] && abs(grid[x][y]-grid[a][b]) <= m;
}

bool bfs(int m) {
    for(int ii = 0; ii < n; ii++) for(int jj = 0; jj < n; jj++) {
        visited[ii][jj] = false;
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(!visited[i][j]) {
        queue<array<int, 2> > q;

        q.push({i, j});
        visited[i][j] = true;
        int c = 1;

        while(!q.empty()) {

            array<int, 2> temp = q.front();
            q.pop();
            int tx = temp[0], ty = temp[1];

            for(int ii = 0; ii < 4; ii++) {
                int nx = tx+dir[ii][0], ny = ty+dir[ii][1];
                if(valid(nx, ny, m, tx, ty)) {
                    ++c;
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }

        if(c >= (n * n + 1) / 2) {
            return true;
        }

    }
    return false;

}
 void setIO(string s) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
    setIO("tractor");
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
        cin >> grid[i][j];
        maxi = max(maxi, grid[i][j]);
    }


    int left = 0, right = maxi;

    while(left < right) {

        int mid = (left + right) / 2;
        if(!bfs(mid)) {
            left = mid + 1;
        }
        else {
            right = mid;
        }

    }

    cout << left << endl;
}