#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 2505
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define ll long long
ll ans;
int valid[maxn][maxn], valend[maxn][maxn];
bool valbgn[maxn][maxn];
int n, m, A[maxn][maxn];
ll f(int x){
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
valid[i][j] = valend[i][j] = valbgn[i][j] = 0;
for(int i=1; i<n-1; i++){
int mx = A[i][x];
valend[i][x-1] = 1;
valbgn[i][x-1] = 1;
for(int j=x; j<m-1; j++){
if( A[i][j] > mx ) mx = A[i][j];
valid[i][j] = ( mx < A[i][x-1] && mx < A[i][j+1] );
valend[i][j] = ( ( ( valend[i][j-1] - valend[i-1][j-1] + ( j - 1 < x ) ) != 0 ) && A[i][j] < A[i-1][j] );
valbgn[i][j] = ( valbgn[i][j-1] && A[i][j] < A[i+1][j] );
if( valid[i][j] ) valid[i][j] += valid[i-1][j];
valend[i][j] += valend[i-1][j];
}
}
ll res = 0;
for(int j=x; j<m-1; j++){
for(int i=1; i<n-1; i++){
if( valbgn[i][j] ){
int k = i - valid[i][j];
res += valend[i][j] - valend[k][j];
//if( valend[i][j] - valend[k][j] ){
// db(x)db(j)
// db(i)db(k)
// db(valend[i][j] - valend[k][j])
//}
}
}
}
return res;
}
long long count_rectangles(std::vector<std::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][j] = a[i][j];
for(int i=1; i<m-1; i++){
ans += f(i);
}
return ans;
}
