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

const int MX=705;

int cnt[MX][MX], mx[MX];

int N,M;

long long count_rectangles(std::vector<std::vector<int> > a) {
	N=a.size();
	M=a[0].size();

	int ans=0;

	for(int l=0;l+2<M;l++) {
		for(int i=0;i<N;i++) {
			for(int j=0;j<MX;j++) {
				cnt[i][j]=0;
			}
			mx[i]=0;
		}

		for(int i=0;i<N;i++) {
			mx[i]=max(mx[i],a[i][l+1]);
		}

		for(int r=l+2;r<M;r++) {
			vector<bool> can;
			vector<int> lst;
			for(int i=0;i<N;i++) {
				if(mx[i]<min(a[i][l],a[i][r])) can.push_back(true);
				else can.push_back(false);

				if(can.back()) {
					if(lst.size()) {
						lst.push_back(min(lst.back(),i));
					} else {
						lst.push_back(i);
					}
				} else {
					lst.push_back(1e9);
				}
			}

			vector<int> stk;
			for(int i=0;i<N;i++) {
				while(stk.size() && a[stk.back()][r-1]<=a[i][r-1]) {
					cnt[stk.back()][i]++;
					if(cnt[stk.back()][i]==r-l-1) ans += i>0 && (stk.back()+1>=lst[i-1]) && stk.back()+1<i;

					stk.pop_back();
				}

				if(stk.size()) {
					cnt[stk.back()][i]++;
					if(cnt[stk.back()][i]==r-l-1) ans += i>0 && (stk.back()+1>=lst[i-1]) && stk.back()+1<i;
				}
				stk.push_back(i);
			}

			for(int i=0;i<N;i++) {
				mx[i]=max(mx[i],a[i][r]);
			}
		}
	}

	return ans;
}