#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 = 2502;
int n, m;
int pref[mxN][mxN], fen[mxN][mxN];
vector<int> row[mxN][mxN], col[mxN][mxN];
set<pair<int,int>> found[mxN][mxN];

struct Fenwick{
	int fen[mxN];
	void upd(int x, int v){
		for(++x; x<mxN; x+=x&-x) fen[x]+=v;
	}
	int sum(int x){
		int s = 0;
		for(++x; x>0; x-=x&-x) s+=fen[x];
		return s;
	}
	int sum(int l, int r){
		if(l>r)return 0;
		return sum(r)-sum(l-1);
	}
} fenc[mxN], fenr[mxN];

ll count_rectangles(vector<vi> a) {
	n = sz(a); m = sz(a[0]);
	ll ans = 0;
	for(int i = 0; i < n; i++){
		stack<int> S = stack<int>();
		for(int j = m-1; j >= 0; j--){
			while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-j)>1){
				row[i][j].pb(S.top());
			}
			S.push(j);
		}
		S = stack<int>();
		for(int j = 0; j < m; j++){
			while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-j)>1){
				if(a[i][S.top()]!=a[i][j]) 
					row[i][S.top()].pb(j);
			}
			S.push(j);
		}
	}
	for(int j = 0; j < m; j++){
		stack<int> S = stack<int>();
		for(int i = n-1; i >= 0; i--){
			while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-i)>1){
				col[i][j].pb(S.top());
			}
			S.push(i);
		}
		S = stack<int>();
		for(int i = 0; i < n; i++){
			while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-i)>1){
				if(a[S.top()][j]!=a[i][j])
					col[S.top()][j].pb(i);
			}
			S.push(i);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			sort(all(row[i][j])),sort(all(col[i][j]));
			if(!sz(row[i][j])) continue;
		}
	}
	for(int i = 1; i < n-1; i++){
		for(int j = 0; j < m; j++)
			for(auto u : col[i-1][j]) fenc[u].upd(j,1);
		for(int j = 0; j < m; j++){
			int k = i;
			
			for(auto k : row[i][j]){
				int R = i+1;
				if(i>1 and binary_search(all(row[i-1][j]),k)){
					R = found[i-1][j].lower_bound({k,-1})->second;
				}
				else{
					while(R<n and binary_search(all(row[R][j]),k)) R++;
					found[i][j].insert({k,R});
				}
				//we have fixed col j... k and upper_row i
			    
			    for(auto l : col[i-1][j+1]){
					if(fenc[l].sum(j+1,k-1)!=k-j-1) continue;
					if(l>R) break; ans++;
				}
			}
			for(auto u : col[i-1][j]) fenc[u].upd(j,-1);
		}
	}
	return ans;
}