#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1145140
#define MINN -1
inline int read() {
	char ch = getchar();
	int x = 0, m = 1;
	while (!isdigit(ch)) {
		if (ch == '-') m = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * m;
}
inline void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
int n, l = MAXN, r = MINN;
int xpos[] = {0, 0, 1, 0, -1}, ypos[] = {0, 1, 0, -1, 0};
map<int, int> mm;
bool flag[10001][10001];
int mapp[10001][10001];
inline int dfs(int x, int y, int d) {
	int sum = 1;
	flag[x][y] = 1;
	for (int i = 1; i <= 4; i++) {
		int px = x + xpos[i];
		int py = y + ypos[i];
		if (abs(mapp[x][y] - mapp[px][py]) <= d && px >= 1 && py >= 1 && px <= n && py <= n && !flag[px][py])sum += dfs(px, py, d);
	}
	return sum;
}
inline bool chkans(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;
}
signed main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			mapp[i][j] = read();
			l = min(mapp[i][j], l);
			r = max(mapp[i][j], r);
		}
	}
	int ans = 1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (chkans(mid) == 1) {
			r = mid - 1, ans = mid;
		} else {
			l = mid + 1;
		}
	}
	write(ans);
	return 0;
}