#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
bool flag[1010][1010];
int mp[1010][1010];
int n,r=-1,l=1e6;
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<=n&&tx>=1&&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()
{
	cin>>n;
	for(int i=1; i<=n; i++)
		for(int j=1; i<=n; j++) {
			cin>>mp[i][j];
			l=min(mp[i][j],l);
			r=max(mp[i][j],r);
		}
	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;
}