#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
const int N = 2500 + 3;
vector<vector<int>> a;
int n, m;
int u[N][N], d[N][N], l[N][N], r[N][N];
void init(){
stack<int> st;
for(int j = 0; j < m; ++j){
for(int i = 0; i < n; ++i){
while(!st.empty() && a[i][j] > a[st.top()][j]){
d[st.top()][j] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
d[st.top()][j] = n;
st.pop();
}
for(int i = n - 1; i >= 0; --i){
while(!st.empty() && a[i][j] > a[st.top()][j]){
u[st.top()][j] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
u[st.top()][j] = -1;
st.pop();
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
while(!st.empty() && a[i][j] > a[i][st.top()]){
r[i][st.top()] = j;
st.pop();
}
st.push(j);
}
while(!st.empty()){
r[i][st.top()] = m;
st.pop();
}
for(int j = n - 1; j >= 0; --j){
while(!st.empty() && a[i][j] > a[i][st.top()]){
l[i][st.top()] = j;
st.pop();
}
st.push(j);
}
while(!st.empty()){
l[i][st.top()] = -1;
st.pop();
}
}
}
bool check(int x1, int y1, int x2, int y2){
for(int i = x1; i <= x2; ++i)
for(int j = y1; j <= y2; ++j)
if(a[i][j] >= a[x1 - 1][j] || a[i][j] >= a[x2 + 1][j] || a[i][j] >= a[i][y1 - 1] || a[i][j] >= a[i][y2 + 1])
return false;
return true;
}
long long count_rectangles(vector<vector<int>> _a) {
swap(a, _a);
n = a.size(), m = a[0].size();
init();
ll ans = 0;
vector<array<int, 4>> v;
for(int x = 1; x < n - 1; ++x)
for(int y = 1; y < m - 1; ++y)
v.push_back({u[x][y] + 1, l[x][y] + 1, d[x][y] - 1, r[x][y] - 1});
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(auto [x1, y1, x2, y2]: v){
if(x1 <= 0 || y1 <= 0 || x2 >= n - 1 || y2 >= m - 1) continue;
//cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
ans += check(x1, y1, x2, y2);
}
return ans;
}
