#include<iostream> #include<iomanip> #include<cmath> #include<string> #include<vector> #include<algorithm> #include<map> #include<queue> #include<stack> using namespace std; typedef long long ll; #define fi first #define se second #define mp make_pair const int inf=1e9+7; const ll mod=1e9+7; int main() { int N; cin>>N; vector<vector<pair<int, int> > >arr(N); int tmp; for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ cin>>tmp; tmp--; arr[tmp].push_back(make_pair(i, j)); } } int up[N][N+1]; int down[N][N+1]; int imosu[N][N]; for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ up[i][j] = 0; down[i][j] = 0; imosu[i][j] = 0; } } int ans = 0; for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ ans += arr[i][j].se; if(arr[i][j].fi+arr[i][j].se>=N){ down[i][N]++; } else{ down[i][arr[i][j].fi+arr[i][j].se+1]++; } if(arr[i][j].fi-arr[i][j].se<0){ up[i][0]++; } else{ up[i][arr[i][j].fi-arr[i][j].se]++; imosu[i][0] += arr[i][j].fi-arr[i][j].se; } } } for(int i=0;i<N;++i){ for(int j=1;j<N;++j){ up[i][j] = up[i][j] + up[i][j-1]; down[i][j] = down[i][j] + down[i][j-1]; } } /** //cout<<endl; for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ cout<<up[i][j]<<" "; } cout<<endl; } cout<<endl; for(int i=0;i<N;++i){ for(int j=0;j<N;++j){ cout<<down[i][j]<<" "; } cout<<endl; } cout<<endl; **/ for(int i=0;i<N;++i){ for(int j=1;j<N;++j){ imosu[i][j] = imosu[i][j-1] - (N-up[i][j-1]) + down[i][j]; } } int maximo; for(int i=0;i<N;++i){ maximo = N*N; for(int j=0;j<N;++j){ //cout<<imosu[i][j]<<" "; if(maximo>imosu[i][j])maximo = imosu[i][j]; } //cout<<endl; ans += maximo; } //cout<<endl; cout<<ans<<endl; }