#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
//#define mp make_pair
//#define OO(x) fixed<<setprecision(x)
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=4040,N=2002*2002;
int X[N],Y[N];
bitset<2001> gl[M],gr[M],bl[M],br[M],t;
bool c[M][M],ok[M][M];
int l=1,r=0,qx[N],qy[N],ans,n;
void push(int x,int y){		
//	assert(x<y);
	qx[++r]=x; qy[r]=y; bl[x][y>>1]=0; br[y][x>>1]=0;
	gl[x][y>>1]=1; gr[y][x>>1]=1; ok[x][y]=1;
}
void refresh(){
	while (l<=r){
		int x=qx[l],y=qy[l++];
//		cout<<x<<" "<<y<<" relax \n";
		if (x==1 && y==n){
			cout<<ans<<"\n";
			exit(0);
		}
		if (x>1 && y<n && c[x-1][y+1]){
			push(x-1,y+1);
		}
		if (x>1){
			t=br[y]&gr[x-1];
			for (int ps=t._Find_first();ps<2001;ps=t._Find_next(ps)){
				push(ps*2+(!(y&1)),y);
			}
		}
		if (y<n){
			t=bl[x]&gl[y+1];
			for (int ps=t._Find_first();ps<2001;ps=t._Find_next(ps)){
				push(x,ps*2+(!(x&1)));
			}
		}
	}
}


int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	F(i,1,n){
		for (int j=i+1;j<=n;j+=2){
			int x=read();
			X[x]=i; Y[x]=j;
			bl[i][j>>1]=1;
			br[j][i>>1]=1;
		}
	}
	F(i,1,n*n/4){
		ans=i;
		c[X[i]][Y[i]]=1;
		if (X[i]+1==Y[i] || ok[X[i]+1][Y[i]-1]){
			push(X[i],Y[i]);
			refresh();
		}
	}
	return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/