#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long count_rectangles (vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<int>> nextLeft(n,vector<int>(m,1e9)), nextRight(n,vector<int>(m,-1)), nextUp(n,vector<int>(m,1e9)), nextDown(n,vector<int>(m,-1)), upFromLeft(n,vector<int>(m)),upFromRight(n,vector<int>(m)),leftFromDown(n,vector<int>(m)),leftFromUp(n,vector<int>(m));
vector<vector<vector<int>>> pushDown(n,vector<vector<int>>(m)), pushRight(n,vector<vector<int>>(m));
for (int i = 0; i < n; i++) {
vector<int> stk;
for (int j = 0; j < m; j++) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextLeft[i][j] = stk.back();
pushRight[i][stk.back()].push_back(j);
upFromLeft[i][j] = 1;
if (i > 0 && nextLeft[i-1][j] == nextLeft[i][j]) upFromLeft[i][j] += upFromLeft[i-1][j];
else if (i > 0 && nextRight[i-1][stk.back()] == j) upFromLeft[i][j] += upFromRight[i-1][stk.back()];
}
stk.push_back(j);
}
stk.clear();
for (int j = m-1; j >= 0; j--) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextRight[i][j] = stk.back();
pushRight[i][j].push_back(stk.back());
upFromRight[i][j] = 1;
if (i > 0 && nextRight[i-1][j] == nextRight[i][j]) upFromRight[i][j] += upFromRight[i-1][j];
else if (i > 0 && nextLeft[i-1][stk.back()] == j) upFromRight[i][j] += upFromLeft[i-1][stk.back()];
}
stk.push_back(j);
}
}
for (int j = 0; j < m; j++) {
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextUp[i][j] = stk.back();
pushDown[stk.back()][j].push_back(i);
leftFromUp[i][j] = 1;
if (j > 0 && nextUp[i][j-1] == nextUp[i][j]) leftFromUp[i][j] += leftFromUp[i][j-1];
else if (j > 0 && nextDown[stk.back()][j-1] == i) leftFromUp[i][j] += leftFromDown[stk.back()][j-1];
}
stk.push_back(i);
}
stk.clear();
for (int i = n-1; i >= 0; i--) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextDown[i][j] = stk.back();
pushDown[i][j].push_back(stk.back());
leftFromDown[i][j] = 1;
if (j > 0 && nextDown[i][j-1] == nextDown[i][j]) leftFromDown[i][j] += leftFromDown[i][j-1];
else if (j > 0 && nextUp[stk.back()][j-1] == i) leftFromDown[i][j] += leftFromUp[stk.back()][j-1];
}
stk.push_back(i);
}
}
auto works = [&] (int bx, int ry, int tx, int ly) {
return ((nextLeft[bx-1][ry] == ly && bx - upFromLeft[bx-1][ry] <= tx + 1) || (nextRight[bx-1][ly] == ry && bx - upFromRight[bx-1][ly] <= tx + 1)) && ((nextUp[bx][ry-1] == tx && ry - leftFromUp[bx][ry-1] <= ly + 1) || (nextDown[tx][ry-1] == bx && ry - leftFromDown[tx][ry-1] <= ly + 1));
};
long long ret = 0;
for (int i = 0; i + 1 < n; i++) {
for (int j = 0; j + 1 < m; j++) {
for (int x : pushDown[i][j+1]) {
for (int y : pushRight[i+1][j]) {
if (abs(i-x) <= 1 || abs(j-y) <= 1 || x < 0 || x > 1e8 || y < 0 || y > 1e8) continue;
int bx = max(x,i), tx = min(x,i), ly = min(y,j), ry = max(y,j);
ret += works(bx,ry,tx,ly);
}
}
}
}
return ret;
}
