#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];

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]));
			}
		}
	}
	long long ans=0;
	for(int lx=1;lx<n-1;lx++){
		for(int ry=1;ry<m-1;ry++){
			for(int rx=lx;rx<n-1;rx++){
				if(!R[ry][lx][rx])rig[lx][rx]=ry;
			}
			for(int ly=1;ly<=ry;ly++){
				for(int rx=lx;rx<n-1;rx++){
					if(!L[rx][ly][ry])break;
					if(rig[lx][rx]<ly)ans++;
				}
			}
		}
	}
	return ans;
}