#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 2600;
int a[N][N],n,m;
int Rg[N][N],Lg[N][N],Rh[N][N],Lh[N][N],mxg[N][N][13],mxh[N][N][13],st[N],st1[N];
void buildg(int r) {
int tek = 1;
for(int i = 1;i <= m;i++)mxg[r][i][0] = a[r][i];
st[1] = 0;
st1[0] = 1;
for(int j = 1;j < 13;j++) {
if(tek * 2 > m)break;
for(int i = 1;i <= m - 2 * tek + 1;i++) {
mxg[r][i][j] = max(mxg[r][i][j - 1],mxg[r][i + tek][j - 1]);
}
tek *= 2;
st1[j] = tek;
for(int i = tek;i < min(m + 1,tek * 2);i++)st[i] = j;
}
}
void buildh(int c) {
int tek = 1;
for(int i = 1;i <= n;i++)mxh[c][i][0] = a[i][c];
st[1] = 0;
st1[0] = 1;
for(int j = 1;j < 13;j++) {
if(tek * 2 > n)break;
for(int i = 1;i <= n - 2 * tek + 1;i++) {
mxh[c][i][j] = max(mxh[c][i][j - 1],mxh[c][i + tek][j - 1]);
}
tek *= 2;
st1[j] = tek;
for(int i = tek;i < min(n + 1,tek * 2);i++)st[i] = j;
}
}
int getg(int rc,int l,int r) {
int k = st[r - l + 1];
return max(mxg[rc][l][k],mxg[rc][r - st1[k] + 1][k]);
}
int geth(int c,int l,int r) {
int k = st[r - l + 1];
return max(mxh[c][l][k],mxh[c][r - st1[k] + 1][k]);
}
void build_cell(int x,int y) {
Rg[x][y] = m;
Lg[x][y] = 1;
Rh[x][y] = n;
Lh[x][y] = 1;
int l = y + 1,r = m;
while(l <= r) {
int mid = (l + r) / 2;
if(getg(x,y + 1,mid) >= a[x][y]) {
Rg[x][y] = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
l = 1,r = y - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(getg(x,mid,y - 1) >= a[x][y]) {
Lg[x][y] = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
l = x + 1,r = n;
while(l <= r) {
int mid = (l + r) / 2;
if(geth(y,x + 1,mid) >= a[x][y]) {
Rh[x][y] = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
l = 1,r = x - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(geth(y,mid,x - 1) >= a[x][y]) {
Lh[x][y] = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
}
int t[N * 4];
vector <int> dob[N];
ll ans;
int Rtemp[N],Ltemp[N];
void build(int v,int tl,int tr) {
t[v] = 0;
if(tl == tr)return;
int tm = (tl + tr) / 2;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
}
void upd(int v,int tl,int tr,int pos) {
if(tl == tr) {
t[v]++;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)upd(v + v,tl,tm,pos);
else upd(v + v + 1,tm + 1,tr,pos);
t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int l,int r) {
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return t[v];
int tm = (tl + tr) / 2;
return get(v + v,tl,tm,l,r) + get(v + v + 1,tm + 1,tr,l,r);
}
void calc1(int L,int R,int l,int r) {
if(r - l + 1 < 3 || R - L + 1 < 3)return;
for(int i = r;i > l + 1;i--)dob[max(l,Ltemp[i])].pb(i);
for(int i = l;i < r - 1;i++) {
while(!dob[i].empty()) {
upd(1,1,m,dob[i].back());
dob[i].pop_back();
}
int curR = min(r,Rtemp[i]);
ans += get(1,1,m,i + 2,curR);
}
dob[r - 1].clear();
dob[r].clear();
}
void calc(int L) {
for(int i = 1;i <= m;i++) {
Rtemp[i] = m;
Ltemp[i] = 1;
}
for(int i = L + 2;i <= n;i++) {
build(1,1,m);
int l = 1;
dob[1].clear();
Ltemp[1] = max(Ltemp[1],Lg[i - 1][1]);
Rtemp[1] = min(Rtemp[1],Rg[i - 1][1]);
for(int j = 2;j <= m;j++) {
dob[j].clear();
Ltemp[j] = max(Ltemp[j],Lg[i - 1][j]);
Rtemp[j] = min(Rtemp[j],Rg[i - 1][j]);
if(Rh[L][j] < i || Lh[i][j] > L) {
int r = j;
calc1(L,i,l,r);
//cout << L << " " << i << " " << l << " " << r << " " << ans << " " << Ltemp[r] << en;
l = j;
continue;
}
}
if(l <= m)calc1(L,i,l,m);
}
}
ll count_rectangles(vector<vector<int> > A) {
n = A.size();
m = A[0].size();
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
a[i + 1][j + 1] = A[i][j];
}
}
for(int i = 1;i <= n;i++)buildg(i);
for(int i = 1;i <= m;i++)buildh(i);
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
build_cell(i,j);
}
}
for(int i = 1;i < n - 1;i++)calc(i);
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
