#include <bits/stdc++.h>
#include "rect.h"
#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
int n, m;
bool valid(std::vector<std::vector<int> > &a, int i, int j){
if(i<1 || i>n-2 || j<1 || j>m-2)
return 0;
return min(min(a[i+1][j],a[i-1][j]),min(a[i][j+1],a[i][j-1]))>a[i][j];
}
ll cre(ll w, ll mx, ll mi){
return (mx-mi)*(w+1)*w/2;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n=SZ(a);
m=SZ(a[0]);
std::vector<std::vector<int> > p(n, std::vector<int> (m,0));
for(int i=1; i<m-1; i++)
if(valid(a,1,i))
p[1][i]=1;
for(int i=2; i<n-1; i++)
for(int j=1; j<m-1; j++)
if(valid(a,i,j))
p[i][j]=p[i-1][j]+1;
ll cc=0;
for(int i=1; i<n-1; i++){
std::vector<ii> s(m-2);
std::vector<int> ne(m-2), pr(m-2);
iota(ALL(ne),0);
iota(ALL(pr),0);
for(int j=0; j<SZ(s); j++)
s[j]={p[i][j+1],j};
sort(ALL(s));
reverse(ALL(s));
std::vector<int> td;
for(int j=0; j<SZ(s); j++){
if(j && s[j].F<s[j-1].F){
while (!td.empty()){
int x=td.back();
cc+=cre(ne[x]-pr[x]-1,p[i][x],s[j].F);
while (!td.empty() && td.back()>pr[x])
td.pop_back();
}
}
int x=s[j].S;
td.PB(x);
if(x<m-3 && ne[x+1]<m-2)
ne[x]=ne[ne[x+1]];
else
ne[x]=m-2;
if(x>0 && pr[x-1]>=0)
pr[x]=pr[pr[x-1]];
else
pr[x]=-1;
}
while (!td.empty()){
int x=td.back();
cc+=cre(ne[x]-pr[x]-1,p[i][x],0);
while (!td.empty() && td.back()>pr[x])
td.pop_back();
}
}
return cc;
}
