U469636 上山岗

给定正整数 $n$。考虑一个包含 $1$ 到 $n^2$ 所有整数的 $n\times n$ 方格表，每个方格内恰有一个数字。称数字比所有相邻方格内的数字都小的方格为“山谷”。一条“上坡路径”是包含一个或多个方格的序列，满足序列中第一个方格是山谷，序列中相邻的两个方格在表格中也相邻，且序列中方格内所写的数字递增。请构造一个方格表，使得上坡路径的数量最小。

一行一个正整数 $n$。

$n$ 行，每行 $n$ 个正整数，表示你构造的方格表。

$1\le n\le 2000$。