#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

#define FOR(i,a,b) for(short i=a; i<=b; ++i)
#define endl '\n'
#define x    first
#define y    second
const short max_n = 500;

short n;
long MAX = 0;
long a[max_n+2][max_n+2];
bool check[max_n+1][max_n+1];

void debug(long high, long cnt)
{
    cerr << endl;
    cerr << "high: " << high << endl;
    cerr << "cnt: " << cnt << endl;
    FOR(i,1,n)
    {
        FOR(j,1,n) cerr << check[i][j] << ' ';
        cerr << endl;
    }
    system("pause");
}

void inp()
{
  //  freopen("ROBOT.INP", "r", stdin);
  //  freopen("ROBOT.OUT", "w", stdout);

    cin >> n;
    FOR(i,1,n)
        FOR(j,1,n)
        {
            cin >> a[i][j];
            MAX = max(MAX, a[i][j]);
        }

    FOR(i,1,n)
    {
        a[0][i] = -1;
        a[n+1][i] = -1;
        a[i][0] = -1;
        a[i][n+1] = -1;
    }
}

long BFS(short x, short y, long high)
{
    queue< pair<long, long> > q;
    short Ox[4] = {0, 0, -1, 1};
    short Oy[4] = {1, -1, 0, 0};

    q.push({x,y});
    long cnt = 1;
    check[x][y] = true;
    while (!q.empty())
    {
        pair <short, short> top;
        top = q.front(); q.pop();

        FOR(i,0,3)
        {
            short xx = top.x + Oy[i];
            short yy = top.y + Ox[i];

            if (a[xx][yy]!=-1 && !check[xx][yy] && abs(a[xx][yy] - a[x][y]) <= high)
            {
                ++cnt;
                q.push({xx,yy});
                check[xx][yy] = true;
            }
        }
    }
   // debug(high, cnt);
    return cnt;
}

bool check_high(long high)
{
    memset(check, false, sizeof(check));
    FOR(i, 1, n)
        FOR(j, 1, n)
            if (!check[i][j])
                if (BFS(i,j, high) >= floor(n*n/2.0d)) return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    inp();

    long l = 0, r = MAX, res = 0;
    while (l<=r)
    {
        long mid = (l+r) / 2;
        if (check_high(mid))
        {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    cout << res;

    return 0;
}