#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2501;
int n,m;
vector<int> col[MAXN][MAXN];
vector<int> row[MAXN][MAXN];
int haha[MAXN][MAXN];
int b0[MAXN][MAXN];
int b1[MAXN][MAXN];
int b2[MAXN][MAXN];
int b3[MAXN][MAXN];
void calc0(int x) {
stack<pair<int,int>> idk;
for(int i = 0; i < m; i++) {
int a = haha[x][i];
while(!idk.empty() && idk.top().first < a) {
b0[x][idk.top().second] = i;
idk.pop();
}
if(!idk.empty()) {
col[idk.top().second][i].push_back(x);
}
idk.push({a,i});
}
}
void calc1(int y) {
stack<pair<int,int>> idk;
for(int i = 0; i < n; i++) {
int a = haha[i][y];
while(!idk.empty() && idk.top().first < a) {
b1[idk.top().second][y] = i;
idk.pop();
}
if(!idk.empty()) {
row[idk.top().second][i].push_back(y);
}
idk.push({a,i});
}
}
void calc2(int x) {
stack<pair<int,int>> idk;
for(int i = m-1; i >= 0; i--) {
int a = haha[x][i];
while(!idk.empty() && idk.top().first < a) {
b2[x][idk.top().second] = i;
idk.pop();
}
if(!idk.empty() && idk.top().first != a) {
col[i][idk.top().second].push_back(x);
}
idk.push({a,i});
}
}
void calc3(int y) {
stack<pair<int,int>> idk;
for(int i = n-1; i >= 0; i--) {
int a = haha[i][y];
while(!idk.empty() && idk.top().first < a) {
b3[idk.top().second][y] = i;
idk.pop();
}
if(!idk.empty() && idk.top().first != a) {
row[i][idk.top().second].push_back(y);
}
idk.push({a,i});
}
}
int dude(vector<int>& wut, int x) {
if(wut.empty()) {
return -1;
}
int l = 0,r = wut.size()-1;
while(l < r) {
int mid = (l+r+1)/2;
if(wut[mid] <= x) {
l = mid;
}
else {
r = mid-1;
}
}
if(wut[l] == x) {
return l;
}
return -1;
}
bool check(int r1, int r2, int c1, int c2) {
int a = dude(col[c1][c2],r1+1),b = dude(col[c1][c2],r2-1);
if(a == -1 || b == -1 || b-a != r2-r1-2) {
return false;
}
a = dude(row[r1][r2],c1+1),b = dude(row[r1][r2],c2-1);
if(a == -1 || b == -1 || b-a != c2-c1-2) {
return false;
}
return true;
}
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++) {
b0[i][j] = -1;
b1[i][j] = -1;
b2[i][j] = -1;
b3[i][j] = -1;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
haha[i][j] = a[i][j];
}
}
for(int i = 0; i < n; i++) {
calc0(i);
calc2(i);
}
for(int i = 0; i < m; i++) {
calc1(i);
calc3(i);
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int x = i+2; x < n; x++) {
for(int y = j+2; y < m; y++) {
if(check(i,x,j,y)) {
ans++;
}
}
}
}
}
return ans;
}
