// the edges are the walls!
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> A;
int N, M;
struct seg {
vector<int> tree;
bool minmax;
int neut;
int op(int a, int b) {
if (minmax) return max(a,b);
return min(a,b);
}
void update(int v, int rl, int rr, int pos, int x) {
if (rl == rr) {
tree[v] = x;
return;
}
int rm = (rl + rr)/2;
if (pos <= rm) update(v*2, rl, rm, pos, x);
else update(v*2+1, rm+1, rr, pos, x);
tree[v] = op(tree[v*2], tree[v*2+1]);
}
int query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return neut;
if (rl == ql && rr == qr) return tree[v];
int rm = (rl + rr) / 2;
return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
}
void init(int n, vector<int> a, bool type) {
minmax = type;
if (type) neut = -1e9;
else neut = 1e9;
tree.assign(n*4, 0);
for (int i = 0; i<n; i++) update(1, 0, n-1, i, a[i]);
}
};
vector<vector<array<int, 4>>> howFar; // 1,0; 0,1; -1,0; 0,-1;
void makeHowFar() {
howFar.assign(N, vector<array<int, 4>>(M));
for (int i = 0; i<N; i++) {
set<pair<int, int>> s;
for (int j = 0; j<M; j++) {
while (s.size() && (*s.begin()).first <= A[i][j]) {
howFar[i][(*s.begin()).second][1] = j;
s.erase(s.begin());
}
s.insert({A[i][j], j});
}
for (auto aa: s) {
howFar[i][aa.second][1] = M-1;
}
}
for (int i = 0; i<M; i++) {
set<pair<int, int>> s;
for (int j = 0; j<N; j++) {
while (s.size() && (*s.begin()).first <= A[j][i]) {
howFar[(*s.begin()).second][i][0] = j;
s.erase(s.begin());
}
s.insert({A[j][i], j});
}
for (auto aa: s) {
howFar[aa.second][i][0] = N-1;
}
}
for (int i = 0; i<N; i++) {
set<pair<int, int>> s;
for (int j = M-1; j>=0; j--) {
while (s.size() && (*s.begin()).first <= A[i][j]) {
howFar[i][(*s.begin()).second][3] = j;
s.erase(s.begin());
}
s.insert({A[i][j], j});
}
for (auto aa: s) {
howFar[i][aa.second][3] = 0;
}
}
for (int i = 0; i<M; i++) {
set<pair<int, int>> s;
for (int j = N-1; j>=0; j--) {
while (s.size() && (*s.begin()).first <= A[j][i]) {
howFar[(*s.begin()).second][i][2] = j;
s.erase(s.begin());
}
s.insert({A[j][i], j});
}
for (auto aa: s) {
howFar[aa.second][i][2] = 0;
}
}
}
vector<seg> howFar10, howFar01, howFar_10, howFar0_1;
void makeHowFarSegs() {
howFar10.resize(N);
for (int i = 0; i<N; i++) {
vector<int> a(M);
for (int j = 0; j<M; j++) a[j] = howFar[i][j][0];
howFar10[i].init(M, a, 0);
}
howFar01.resize(M);
for (int i = 0; i<M; i++) {
vector<int> a(N);
for (int j = 0; j<N; j++) a[j] = howFar[j][i][1];
howFar01[i].init(N, a, 0);
}
howFar_10.resize(N);
for (int i = 0; i<N; i++) {
vector<int> a(M);
for (int j = 0; j<M; j++) a[j] = howFar[i][j][2];
howFar_10[i].init(M, a, 1);
}
howFar0_1.resize(M);
for (int i = 0; i<M; i++) {
vector<int> a(N);
for (int j = 0; j<N; j++) a[j] = howFar[j][i][3];
howFar0_1[i].init(N, a, 1);
}
}
bool verify(int top, int bottom, int left, int right) { // top, bottom, left, right
if (bottom-top < 2) return 0;
if (right-left < 2) return 0;
if(!(howFar10[top].query(1, 0, M-1, left+1, right-1) >= bottom)) return 0;
if(!(howFar_10[bottom].query(1, 0, M-1, left+1, right-1) <= top)) return 0;
if(!(howFar01[left].query(1, 0, N-1, top+1, bottom-1) >= right)) return 0;
if(!(howFar0_1[right].query(1, 0, N-1, top+1, bottom-1) <= left)) return 0;
return 1;
}
long long count_rectangles(std::vector<std::vector<int> > _a) {
A = _a;
// for (auto i: A) {for (int j: i) {cerr << j << " ";} cerr << "\n";}
// cerr << "\n";
N = A.size();
M = A[0].size();
makeHowFar();
// for (auto i: howFar) {
// for (auto j: i) {
// for (int k: j) cerr<<k<<",";
// cerr << " ";
// }
// cerr << "\n";
// }
makeHowFarSegs();
int res = 0;
for (int i = 0; i<N; i++) {
for (int j = 0; j<M; j++) {
for (int k = 0; k<N; k++) {
for (int l = 0; l<M; l++) {
res += verify(i,k,j,l);
// if (verify(i,k,j,l)) cerr << i+1 << " " << k-1 << " " << j+1 << " " << l-1 << "\n";
}
}
}
}
return res;
}
