#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 10, inf = 1e9 + 10;
//vector<vector<int>> a;
vector<vector<vector<bool>>> up, l;
vector<vector<vector<int>>> ud, lr;
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
l.resize(n);
for(int i = 0; i < n; ++i){
l[i].resize(m);
for(int j = 0; j < m; ++j)
l[i][j].resize(m);
}
lr.resize(m);
for(int i = 0; i < m; ++i){
lr[i].resize(m);
for(int j = 0; j < m; ++j)
lr[i][j].resize(n);
}
up.resize(m);
for(int i = 0; i < m; ++i){
up[i].resize(n);
for(int j = 0; j < n; ++j)
up[i][j].resize(n);
}
ud.resize(n);
for(int i = 0; i < n; ++i){
ud[i].resize(n);
for(int j = 0; j < n; ++j)
ud[i][j].resize(m);
}
for(int i = 1; i < n; ++i){
for(int j = 1; j < m - 1; ++j){
int maxel = -inf, f = a[i][j - 1];
for(int q = j; q < m - 1; ++q){
maxel = max(maxel, a[i][q]);
if(maxel < f && maxel < a[i][q + 1])
l[i][j][q] = 1;
}
// cout << l[i][j][m - 3] << " ";
}
// cout << endl;
}
for(int i = 1; i < m - 1; ++i)
for(int j = i; j < m - 1; ++j)
for(int q = 1; q < n - 1; ++q)
lr[i][j][q] = lr[i][j][q - 1] + l[q][i][j];
for(int i = 1; i < m; ++i){
for(int j = 1; j < n - 1; ++j){
int maxel = -inf, f = a[j - 1][i];
for(int q = j; q < n - 1; ++q){
maxel = max(maxel, a[q][i]);
if(maxel < f && maxel < a[q + 1][i])
up[i][j][q] = 1;
}
}
}
// cout << up[1][1][1] << " " << up[2][1][1] << endl;
for(int i = 1; i < n - 1; ++i)
for(int j = i; j < n - 1; ++j)
for(int q = 1; q < m - 1; ++q){
ud[i][j][q] = ud[i][j][q - 1] + up[q][i][j];
// cout << i << " " << j << " " << q << " " << ud[i][j][q - 1] << " " << ud[i][j][q] << " " << up[q][i][j] << endl;
}
// cout << ud[1][1][1] << endl;
// cout << ud[1][1][2] << endl;
int ans = 0;
for(int i = 1; i < n - 1; ++i)
for(int j = 1; j < m - 1; ++j)
for(int i1 = i; i1 < n - 1; ++i1)
for(int j1 = j; j1 < m - 1; ++j1){
// if(i == 1 && j == 1 && i1 == 1 && j1 == 2){
// cout << lr[j][j1][i1] - lr[j][j1][i - 1] << " " << ud[i][i1][j1] - ud[i][i1][j - 1] << endl;
// }
if(lr[j][j1][i1] - lr[j][j1][i - 1] == i1 - i + 1 &&
ud[i][i1][j1] - ud[i][i1][j - 1] == j1 - j + 1)
++ans;
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
3 4
14 7 3 6
7 5 2 7
5 13 5 6
*/
