#include "rect.h"
#include <bits/stdc++.h>

#define sz(s) ((int)s.size())

using namespace std;

const int MAX=710;

bool L[MAX][MAX][MAX],R[MAX][MAX][MAX];
int rig[MAX][MAX][MAX];

long long count_rectangles(vector<vector<int>> a) {
	int n=sz(a),m=sz(a[0]);
	for(int i=0;i<n;i++){
		for(int j=1;j<m-1;j++){
			int mx=0;
			for(int k=j;k<m-1;k++){
				mx=max(mx,a[i][k]);
				L[i][j][k]=(mx<min(a[i][j-1],a[i][k+1]));
			}
		}
	}
	for(int i=0;i<m;i++){
		for(int j=1;j<n-1;j++){
			int mx=0;
			for(int k=j;k<n-1;k++){
				mx=max(mx,a[k][i]);
				R[i][j][k]=(mx<min(a[j-1][i],a[k+1][i]));
			}
		}
	}
	for(int j=1;j<n-1;j++){
		for(int k=1;k<n-1;k++){
			for(int i=1;i<m-1;i++){
				if(R[i][j][k])rig[i][j][k]=rig[i-1][j][k];
				else rig[i][j][k]=i;
			}
		}
	}
	long long ans=0;
	for(int lx=1;lx<n-1;lx++){
		for(int ly=1;ly<m-1;ly++){
			for(int ry=ly;ry<m-1;ry++){
				for(int rx=lx;rx<n-1;rx++){
					if(!L[rx][ly][ry])break;
					if(rig[ry][lx][rx]<ly)ans++;
				}
			}
		}
	}
	return ans;
}