#include<bits/stdc++.h>
using namespace std;
int dx[]= {-1,0,0,1};
int dy[]= {0,-1,1,0};
bool flag[1001][1001];
int mp[1001][1001];
int n,r=-1,l=1e6;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int dfs(int x,int y,int k) //x,y 坐标,k 当前得分
{
	int sum=1;
	flag[x][y]=1;
	for(int i=0; i<=3; i++) {
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&tx<=n&&ty<=n&&ty>=1&&abs(mp[tx][ty]-mp[x][y])<=k&&!flag[tx][ty]) sum+=dfs(tx,ty,k);
	}
	return sum;
}
bool change(int x)
{
	memset(flag,0,sizeof(flag));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			if(!flag[i][j]&&dfs(i,j,x)*2>=n*n) {
				return 1;
			}
		}
	return 0;
}
int main()
{
	n=read();
	for(int i=1; i<=n; i++)
		for(int j=1; i<=n; j++) {
			mp[i][j]=read();
			r=max(r,mp[i][j]);
			l=min(l,mp[i][j]);
		}
	int ans=1;
	while(r>=l) {
		int mid=(l+r)/2;
		if(change(mid)) {
			r=mid-1,ans=mid;
		}
		else {
			l=mid+1;
		}
	}
	cout<<ans;
	return 0;
}