#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;

const int mxN = 702;
int n, m;
bitset<mxN> goodr[mxN][mxN];
bitset<mxN> goodc[mxN][mxN];
int badr[mxN][mxN], badc[mxN][mxN];

ll count_rectangles(vector<vi> a) {
	n = sz(a); m = sz(a[0]); ll ans = 0;
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			//nxR[i][j] = next index such that a[i][index] <= a[i][j] or n
			//prR[i][j] = previous index such that a[i][index] <= a[i][j] or 
			// row
			int boundaryR = a[i][j-1], mx = 0;
			badr[i][j]=m-1;
			for(int k = j; k < m-1; k++){
				mx = max(mx,a[i][k]);
				if(boundaryR<=mx){
					badr[i][j]=k;
					break;
				}
				if(a[i][k+1]<=mx) continue; 
				goodr[i][j][k]=1;
			}
			
			// column
			int boundaryC = a[i-1][j]; mx = 0;
			badc[i][j]=n-1;
			for(int k = i; k < n-1; k++){
				mx = max(mx, a[k][j]);
				if(boundaryC<=mx){
					badc[i][j]=k;
					break;
				}
				
				if(a[k+1][j]<=mx) continue;
				goodc[i][j][k]=1;
			}
		}
	}
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			int endK = n-1;
			for(int k = j; k < m-1; k++){
				if(badr[i][j]<=k) break;
				endK = min(endK, badc[i][k]);
				if(!goodr[i][j][k]) continue;
				for(int l = i; l < endK; l++){
					if(!goodr[l][j][k]) break;
					int mn = 1;
					for(int y = j; y <= k; y++)
						mn=min<int>(mn,goodc[i][y][l]);
					if(mn!=1) continue; 
					//cout << i << " " << j << " " << l << " " << k << "\n"; 
					ans++;
				}
			}
		}
	}
	return ans;
}