#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;
vector<vector<vector<int>>> goodc;
vector<vector<bitset<mxN>>> goodr;
vector<vector<int>> badr, badc;

void Rotate(vector<vi> &a){
	vector<vi> b; b.clear();
	for(int i = 0; i < sz(a[0]); i++){
		vi w; w.clear();
		for(int j = 0; j < sz(a); j++){
			w.pb(a[j][i]);
		}
		b.pb(w);
	}
	a.swap(b);
}

ll count_rectangles(vector<vi> a) {
	if(n<m) Rotate(a);
	n = sz(a); m = sz(a[0]); 
	ll ans = 0;
	goodc.resize(n,vector<vi>(m,vi(n,0)));
	goodr.resize(n,vector<bitset<mxN>>(m,bitset<mxN>(0)));
	badr.resize(n,vi(m,0)); badc.resize(n,vi(m,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 k = 0; k < n; k++)
				goodc[i][j][k]+=goodc[i][j-1][k];
		}
	}
	
	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 sum = goodc[i][k][l]-goodc[i][j-1][l];
					if(sum!=k-j+1) continue; 
					//cout << i << " " << j << " " << l << " " << k << "\n"; 
					ans++;
				}
			}
		}
	}
	return ans;
}