mtwalk

//#include<bits/stdc++.h>
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstring>

#define long short
#define nln '\n'

const long N = 111;

using namespace std;

// Global variables: f1, f2, n, mat

fstream f1, f2;

inline void openf()
{
    f1.open("mtwalk.inp", ios:: in);
    f2.open("mtwalk.out", ios:: out);
}

inline void closef()
{
    f1.close();
    f2.close();
}

long n, miv = N, mav = -1;
vector<vector<long>> mat(N);

void data()
{
    f1.tie(0)->sync_with_stdio(0);
    f2.tie(0)->sync_with_stdio(0);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (long i = 0; i != n; ++i)
    {
        for (long j = 0; j != n; ++j)
        {
            long x;
            cin >> x;
            mat[i].push_back(x);
            if (x > mav)
                mav = x;
            if (x < miv)
                miv = x;
        }
    }
}

vector<short> me1 = {0, 1, 0, -1}, me2{1, 0, -1, 0};
vector<vector<bool>> cam(N);

bool dfs(long i, long j, long mid, long mad)
{
    if (i < 0 || i >= n || j < 0 || j >= n)
        return 0;

    if (cam[i][j] || mat[i][j] < mid || mat[i][j] > mad)
        return 0;
    if (i == n-1 && j == n-1) return 1;

    cam[i][j] = 1;

    for (int k = 0; k < 4; k++)
    {
        int u = i + me1[k], v = j + me2[k];
        if (dfs(u, v, mid, mad)) return 1;
    }
  return 0;
}

void init_cam()
{
    for (long i = 0; i != n; ++i)
        cam[i].resize(n, 0);
}

void reset_cam()
{
    for (long i = 0; i != n; ++i)
        for (long j = 0; j != n; ++j)
            cam[i][j] = 0;
}

bool check(long del)
{
    for (long i = miv; i+del-1 != mav+1; ++i)
    {
        reset_cam();
        if (dfs(0, 0, i, i+del))
            return 1;
    }
    return 0;
}

long ans = -1;

void process()
{
    init_cam();
        long lef = 0, rig = 120;
        while (lef <= rig)
        {
            long del = (lef+rig)/2;
            if (check(del))
            {
                ans = del;
                rig = del-1;
            }
            else
                lef = del+1;
        }
}

void view()
{
    cout << ans << nln;
}

int main()
{
    openf();
    data();
    process();
    view();
    closef();
    return 0;
}