#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2507;
const int inf = 1e9;
struct b_str{
int l, r, u, d;
b_str(){}
};
int a[MAXN][MAXN], n, m;
b_str b[MAXN][MAXN];
struct segment_tree{
int mn[4 * MAXN];
char type;
int val;
segment_tree(){}
void init(int idx, int l, int r){
if(l == r){
switch(type){
case 'l':
mn[idx] = b[l][val].l;
case 'r':
mn[idx] = b[l][val].r;
case 'u':
mn[idx] = b[val][l].u;
case 'd':
mn[idx] = b[val][l].d;
}
return;
}
int mid = (l + r) >> 1;
init(2 * idx, l, mid);
init(2 * idx + 1, mid + 1, r);
mn[idx] = min(mn[2 * idx], mn[2 * idx + 1]);
}
void do_init(char type, int val){
this->type = type;
this->val = val;
init(1, 0, MAXN - 1);
}
int query(int idx, int l, int r, int sl, int sr){
if(l > sr || r < sl){
return inf;
}
if(sl <= l && r <= sr){
return mn[idx];
}
int mid = (l + r) >> 1;
int lvalue = query(2 * idx, l, mid, sl, sr);
int rvalue = query(2 * idx + 1, mid + 1, r, sl, sr);
return min(lvalue, rvalue);
}
};
segment_tree st_l[MAXN], st_r[MAXN], st_u[MAXN], st_d[MAXN];
bool check(int x1, int y1, int x2, int y2){
for(int i = x1; i <= x2; ++i){
for(int j = y1; j <= y2; ++j){
int mn = min(min(a[i][y1 - 1], a[i][y2 + 1]), min(a[x1 - 1][j], a[x2 + 1][j]));
if(mn <= a[i][j]){
return false;
}
}
}
return true;
}
long long 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][j] = _a[i][j];
}
}
for(int i = 0; i < n; ++i){
stack<int> st;
st.push(0);
for(int j = 1; j < m; ++j){
while(!st.empty() && a[i][j] >= a[i][st.top()]){
b[i][st.top()].r = j;
st.pop();
}
}
while(!st.empty()){
b[i][st.top()].r = m;
st.pop();
}
}
for(int i = 0; i < n; ++i){
stack<int> st;
st.push(m - 1);
for(int j = m - 2 ; j >= 0; --j){
while(!st.empty() && a[i][j] >= a[i][st.top()]){
b[i][st.top()].l = j;
st.pop();
}
}
while(!st.empty()){
b[i][st.top()].l = -1;
st.pop();
}
}
for(int i = 0; i < m; ++i){
stack<int> st;
st.push(0);
for(int j = 1; j < n; ++j){
while(!st.empty() && a[j][i] >= a[st.top()][i]){
b[st.top()][i].d = j;
st.pop();
}
}
while(!st.empty()){
b[st.top()][i].d = n;
st.pop();
}
}
for(int i = 0; i < m; ++i){
stack<int> st;
st.push(n - 1);
for(int j = n - 2; j >= 0; --j){
while(!st.empty() && a[j][i] >= a[st.top()][i]){
b[st.top()][i].u = j;
st.pop();
}
}
while(!st.empty()){
b[st.top()][i].u = n;
st.pop();
}
}
for(int i = 0; i < n; ++i){
st_u[i].do_init('u', i);
st_d[i].do_init('d', i);
}
for(int i = 0; i < m; ++i){
st_l[i].do_init('l', i);
st_r[i].do_init('r', i);
}
long long ans = 0;
for(int x1 = 1; x1 < n - 1; ++x1){
for(int x2 = x1; x2 < n - 1; ++x2){
for(int y1 = 1; y1 < m - 1; ++y1){
for(int y2 = y1; y2 < m - 1; ++y2){
ans += check(x1, y1, x2, y2);
}
}
}
}
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
*/
