#include "rect.h"
#include <bits/stdc++.h>
#define N 2505
using namespace std;
struct BIT{
vector<int> bit;
int n;
BIT(int size){
n = size;
bit.assign(n+5,0);
}
void upd(int pos,int val){
for(++pos;pos<n;pos += pos & -pos){
bit[pos] += val;
}
}
int get(int pos){
int ret = 0;
for(++pos;pos > 0;pos -= pos & -pos){
ret += bit[pos];
}
return ret;
}
int get(int l,int r){
return get(r) - get(l-1);
}
};
struct SegTree{
vector<BIT> t;
int n;
SegTree(int size){
n = size + 5;
t.assign(4*n,BIT(n));
}
void upd(int v,int tl,int tr,int l,int r,int val){
t[v].upd(r,val);
if(tl == tr)return;
int tm = (tl + tr)/2;
if(l <= tm){
upd(v*2,tl,tm,l,r,val);
}
else upd(v*2+1,tm+1,tr,l,r,val);
}
int get(int v,int tl,int tr,int l,int r){
if(tr <= l){
return t[v].get(r,n-1);
}
if(tl > l){
return 0;
}
int tm = (tl + tr)/2;
return get(v*2,tl,tm,l,r) + get(v*2+1,tm+1,tr,l,r);
}
void upd(int l,int r,int val){
upd(1,0,n-1,l,r,val);
}
int get(int l,int r){
return get(1,0,n-1,l,r);
}
};
int mp[N][N];
vector<int> pos[N];
vector<int> prepos[N];
vector<pair<int,int>> ranges[N][N];
vector<pair<int,int>> queries[N][N];
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
long long ans = 0;
for(int r1 = 1;r1<=n-2;r1++){
for(int r2 = r1;r2 <= n-2;r2++){
for(int c1 = 1;c1<=m-2;c1++){
for(int c2 = c1;c2 <= m-2;c2++){
bool ok = 1;
for(int i = r1;i<=r2;i++){
for(int j = c1;j<=c2;j++){
ok &= a[i][j] < min({a[i][c1-1],a[i][c2+1],a[r1-1][j],a[r2+1][j]});
}
}
ans += ok;
}
}
}
}
return ans;
}
