#include <bits/stdc++.h>
#include "rect.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
int n, m;
vector <vector <int> > a;
vector <int> calc(vector <int> &a, int b, int c){
//~ b = 0 for >
//~ b = 1 for >=
//~ c = 0 for forward
//~ c = 1 for backward
int n = a.size();
vector <int> inds;
for(int i = 0 ; i < n ; i++){
if(c == 0) inds.push_back(i);
else inds.push_back(n - i - 1);
}
vector <int> ret(n);
vector <int> cur;
for(auto &i : inds){
while(cur.size() && a[i] >= a[cur.back()] + b){
cur.pop_back();
}
if(cur.size() == 0) ret[i] = -1;
else ret[i] = cur.back();
cur.push_back(i);
}
return ret;
}
bool check(int r1, int c1, int r2, int c2){
if(r1 == -1 || c1 == -1 || r2 == -1 || c2 == -1) return 0;
for(int i = r1 + 1 ; i < r2 ; i++){
for(int j = c1 + 1 ; j < c2 ; j++){
if(!(a[r1][j] > a[i][j] && a[r2][j] > a[i][j] && a[i][c1] > a[i][j] && a[i][c2] > a[i][j])){
return 0;
}
}
}
return 1;
}
long long count_rectangles(std::vector<std::vector<int> > A) {
a = A;
n = a.size();
m = a[0].size();
vector <vector <int> > us(n, vector <int>(m)), rs(n, vector <int>(m)), ds(n, vector <int>(m)), ls(n, vector <int>(m));
vector <vector <int> > ue(n, vector <int>(m)), re(n, vector <int>(m)), de(n, vector <int>(m)), le(n, vector <int>(m));
for(int i = 0 ; i < n ; i++){
vector <int> cur = a[i];
ls[i] = calc(cur, 0, 0);
le[i] = calc(cur, 1, 0);
rs[i] = calc(cur, 0, 1);
re[i] = calc(cur, 1, 1);
}
for(int j = 0 ; j < m ; j++){
vector <int> cur(n);
for(int i = 0 ; i < n ; i++){
cur[i] = a[i][j];
}
vector <int> g;
g = calc(cur, 0, 0);
for(int i = 0 ; i < n ; i++){
us[i][j] = g[i];
}
g = calc(cur, 1, 0);
for(int i = 0 ; i < n ; i++){
ue[i][j] = g[i];
}
g = calc(cur, 0, 1);
for(int i = 0 ; i < n ; i++){
ds[i][j] = g[i];
}
g = calc(cur, 1, 1);
for(int i = 0 ; i < n ; i++){
de[i][j] = g[i];
}
}
int ret = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
ret += check(us[i][j], ls[i][j], ds[i][j], rs[i][j]);
}
}
return ret;
}
