P10988

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f[1010][1010],a[1010][1010];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	memset(f,1e9,sizeof f);
	for(int i=1;i<=n;i++){
		f[i][1]=i-1;
	}
	f[1][2]=1;
	for(int i=3;i<=n;i++){
		if(a[1][i]<a[1][i-1]){
			if(a[1][i-1]<a[1][i-2]){
				f[1][i]=f[1][i-1];
			}
			else{
				f[1][i]=f[1][i-1]+1;
			}
		}
		else{
			f[1][i]=f[1][i-1]+1;
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			if(j==2){
				f[i][j]=min(f[i-1][j],f[i][j-1])+1;
			}
			else{
				if(a[i][j]>a[i][j-1]){
					if(a[i][j-1]>a[i][j-2]){
						f[i][j]=f[i][j-1];
					}
					else{
						f[i][j]=f[i][j-1]+1;
					}
				}
				else{
					f[i][j]=f[i][j-1]+1;
				}
				f[i][j]=min(f[i][j],min(f[i-1][j],f[i][j-1])+1);
			}
		}
	}
	cout<<f[n][n];
	return 0;
}