#include<bits/stdc++.h>
#include"rect.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2500 + 5;

vector<pii> getseg(const vector<int> &a,int l,int r)
{
	vector<pii> res;
	
	static int sta[MAXN];
	int tp = 0;
	for(int i=l; i<=r; ++i)
	{
		while(tp >= 2 && a[sta[tp]] < a[i])
			--tp, res.emplace_back(sta[tp] + 1, i - 1);
		
		while(tp && a[sta[tp]] <= a[i]) --tp;
		sta[++tp] = i;
	}
	return res;
}

ll count_rectangles(vector< vector<int> > a)
{
	int n = (int)a.size(), m = (int)a[0].size();
	
	static vector< array<int,3> > eff[MAXN];
	
	static int f[2][MAXN][MAXN];
	int now = 0;
	
	vector<pii> lst;
	for(int i=n-2; i>=0; --i)
	{
		now ^= 1;
		auto vec = getseg(a[i], 0, m - 1);
		if(i == 0) vec.clear();
		
		for(auto t: vec)
			f[now][t.first][t.second] = f[now ^ 1][t.first][t.second] + 1;
		
		for(auto t: lst)
		{
			int l = t.first, r = t.second;
			if(!f[now][l][r])
			{
				eff[l].push_back({i + 1, i + f[now^1][l][r], r - l + 1});
			}
			f[now^1][l][r] = 0;
		}
		lst = vec;
	}
	
	vector< vector<int> > b(m, vector<int>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			b[j][i] = a[i][j];
	
	int ans = 0;
	lst.clear();
	for(int i=m-2; i>=1; --i)
	{
		now ^= 1;
		auto vec = getseg(b[i], 0, n - 1);
		
		for(auto t: vec)
			f[now][t.first][t.second] = f[now ^ 1][t.first][t.second] + 1;
		
		for(auto t: eff[i])
		{
			int l = t[0], r = t[1], len = t[2];
			
			auto cur = getseg(b[i], l - 1, r + 1);
			for(auto tt: cur)
			{
				if(f[now][tt.first][tt.second] >= len)
					++ans;
			}
		}
		
		for(auto t: lst)
			f[now^1][t.first][t.second] = 0;
		lst = vec;
	}
	
	return ans;
}