#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];

void upd(int i, int x, int v){
	for(++x; x<mxN; x+=x&-x)
		fen[i][x]+=v;
}

int sum(int i, int x){
	int s = 0;
	for(++x; x>0; x-=x&-x) s+=fen[i][x];
	return s;
}

int sum(int i, int l, int r){
	if(l>r)return 0;
	return sum(i,r)-sum(i,l-1);
}

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 = 1; i < n-1; i++){
		for(int j = 0; j < m; j++)
			for(auto u : col[i-1][j]) upd(u,j,1);
		for(int j = 0; j < m; j++){
			for(auto k : row[i][j]){
				//we have fixed j... k
			    //we have fixed i 
			    
			    for(auto l : col[i-1][j+1]){
					//cout << i << " " << j << " " << k << "\n";
					if(sum(l,j,k)!=k-j-1)continue;
					ans++;
				}
			}
			for(auto u : col[i-1][j]) upd(u,j,-1);
		}
	}
	return ans;
}