#include <bits/stdc++.h>
#include "rect.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
const int N = 2501;
const int INF = (int)1e9;
struct segment{
pair <int, int> tree[4 * N];
//~ mn, mx
segment(){
for(int i = 0 ; i < 4 * N ; i++){
tree[i] = make_pair(INF, -INF);
}
}
pair <int, int> merge(pair <int, int> l, pair <int, int> r){
return make_pair(min(l.first, r.first), max(l.second, r.second));
}
void build(int l, int r, int node, vector <int> &a){
if(l == r){
if(a[l] != -1){
tree[node] = make_pair(a[l], a[l]);
}
return;
}
int mid = (l + r) / 2;
build(l, mid, 2 * node, a);
build(mid + 1, r, 2 * node + 1, a);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
pair <int, int> query(int l, int r, int node, int s, int e){
if(r < l || r < s || l > e) return make_pair(INF, -INF);
if(s <= l && r <= e) return tree[node];
int mid = (l + r) / 2;
return merge(query(l, mid, 2 * node, s, e), query(mid + 1, r, 2 * node + 1, s, e));
}
};
int n, m;
vector <vector <int> > a;
set <pair <pair <int, int>, pair <int, int> > > vis;
vector <vector <int> > us, rs, ds, ls, ue, re, de, le;
vector <segment> ue_tree, re_tree, de_tree, le_tree;
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;
if(vis.count(make_pair(make_pair(r1, c1), make_pair(r2, c2)))) return 0;
vis.insert(make_pair(make_pair(r1, c1), make_pair(r2, c2)));
int v = de_tree[r1].query(0, m - 1, 1, c1 + 1, c2 - 1).first;
if(v < r2) return 0;
v = ue_tree[r2].query(0, m - 1, 1, c1 + 1, c2 - 1).second;
if(v > r1) return 0;
v = re_tree[c1].query(0, n - 1, 1, r1 + 1, r2 - 1).first;
if(v < c2) return 0;
v = le_tree[c2].query(0, n - 1, 1, r1 + 1, r2 - 1).second;
if(v > c1) return 0;
return 1;
}
long long count_rectangles(std::vector<std::vector<int> > A) {
a = A;
n = a.size();
m = a[0].size();
us.resize(n, vector <int>(m));
ue.resize(n, vector <int>(m));
ds.resize(n, vector <int>(m));
de.resize(n, vector <int>(m));
ls.resize(n, vector <int>(m));
le.resize(n, vector <int>(m));
rs.resize(n, vector <int>(m));
re.resize(n, vector <int>(m));
ue_tree.resize(n);
de_tree.resize(n);
le_tree.resize(m);
re_tree.resize(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];
}
}
for(int i = 0 ; i < n ; i++){
ue_tree[i].build(0, m - 1, 1, ue[i]);
de_tree[i].build(0, m - 1, 1, de[i]);
}
for(int j = 0 ; j < m ; j++){
vector <int> cur(n);
for(int i = 0 ; i < n ; i++){
cur[i] = le[i][j];
}
le_tree[j].build(0, n - 1, 1, cur);
cur.assign(n, 0);
for(int i = 0 ; i < n ; i++){
cur[i] = re[i][j];
}
re_tree[j].build(0, n - 1, 1, cur);
}
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;
}
