#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define fr first
#define sc second
#define sz(v) ((int)(v).size())
typedef long long lld;
typedef pair<int, int> pii;
int N, M;
int A[2502][2502];
pii ver[2502][2502], hor[2502][2502];
map <int, int> verDP[2502][2502], horDP[2502][2502];
inline int get(map<int, int> &m, int x)
{
auto it = m.find(x);
return it == m.end() ? 0 : it->second;
}
lld count_rectangles(vector<vector<int>> a)
{
N = sz(a); M = sz(a[0]);
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) A[i][j] = a[i-1][j-1];
for (int i=1;i<=N;i++){
stack <int> stk;
for (int j=1;j<=M;j++){
while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
hor[i][j].fr = stk.empty() ? 1 : stk.top()+1;
stk.push(j);
}
stk = {};
for (int j=M;j;j--){
while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
hor[i][j].sc = stk.empty() ? M : stk.top()-1;
stk.push(j);
}
}
for (int j=1;j<=M;j++){
stack <int> stk;
for (int i=1;i<=N;i++){
while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
ver[i][j].fr = stk.empty() ? 1 : stk.top()+1;
stk.push(i);
}
stk = {};
for (int i=N;i;i--){
while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
ver[i][j].sc = stk.empty() ? N : stk.top()-1;
stk.push(i);
}
}
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
{
const auto &sg = ver[i][j];
verDP[sg.fr][sg.sc][j] = get(verDP[sg.fr][sg.sc], j-1)+1;
}
{
const auto &sg = hor[i][j];
horDP[sg.fr][sg.sc][i] = get(horDP[sg.fr][sg.sc], i-1)+1;
}
}
set <lld> vis;
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
int sy = ver[i][j].fr, ey = ver[i][j].sc;
int sx = hor[i][j].fr, ex = hor[i][j].sc;
if (sy == 1 || ey == N || sx == 1 || ex == M) continue;
if (get(verDP[sy][ey], ex) <= ex-sx || get(horDP[sx][ex], ey) <= ey-sy) continue;
lld v = ((sy-1)*M+sx-1)*N*M + (ey-1)*M+ex-1;
if (vis.count(v)) continue;
vis.insert(v);
}
return sz(vis);
}
