#include "bits/stdc++.h"
#include "rect.h"
using namespace std;
struct rect {
int i, j;
int l, r;
rect (int i, int j, int l, int r) : i(i), j(j), l(l), r(r) {}
rect () {}
};
vector <rect> getLines(vector<std::vector<int>> a) {
int n = a.size();
int m = a.front().size();
vector <int> v[m];
vector <rect> vert;
for(int i = 0; i < n; i++) {
vector <int> last (n, -1);
for(int j = 0; j < m; j++) {
vector <int> aux (n, -1);
while(!v[j].empty() && a[v[j].back()][j] < a[i][j]) {
aux[v[j].back()] = 1;
v[j].pop_back();
}
if(not v[j].empty()) {
aux[v[j].back()] = 1;
}
v[j].push_back(i);
for(int k = 0; k < i; k++) {
if(last[k] != -1) {
if(aux[k] == -1) {
if(k - 1 < i) vert.push_back(rect(k, i, last[k], j - 1));
last[k] = -1;
}
} else if (aux[k] == 1) {
last[k] = j;
}
}
}
for(int k = 0; k < i; k++) {
if(last[k] != -1) {
if(k < i - 1) vert.push_back(rect(k, i, last[k], m - 1));
}
}
}
return vert;
}
vector <vector <int>> rotate(vector <vector <int>> a) {
int n = a.size();
int m = a.front().size();
vector <vector <int>> b (m, vector <int> (n, 0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
b[i][j] = a[j][i];
}
}
return b;
}
/*
0 2 1 2
2 4 0 1
1 4 4 4
*/
long long count_rectangles(vector <vector <int>> a) {
auto h = getLines(a);
auto v = getLines(rotate(a));
for(auto &x : v) {
x.l -= 1;
x.r += 1;
}
for(auto &x : h) {
x.l -= 1;
x.r += 1;
}
long long ans = 0;
for(auto x : v) {
for(auto y : h) {
if(x.l <= y.i && y.j <= x.r) {
if(y.l <= x.i && x.j <= y.r) {
++ans;
}
}
}
}
return ans;
}
