#include "rect.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int count_rectangles(vector<vector<signed>> a) {
int nbLig = a.size(), nbCol = a[0].size();
vector<vector<int>> down(nbLig, vector<int>(nbCol));
vector<vector<int>> up(nbLig, vector<int>(nbCol));
vector<vector<int>> right(nbLig, vector<int>(nbCol));
vector<vector<int>> left(nbLig, vector<int>(nbCol));
for (int col = 0; col < nbCol; ++col) {
for (int iLig = nbLig - 1; iLig >= 0; --iLig) {
int nxt = iLig + 1;
while (nxt < nbLig and a[iLig][col] > a[nxt][col])
nxt = down[nxt][col];
down[iLig][col] = nxt;
}
for (int iLig = 0; iLig < nbLig; ++iLig) {
int nxt = iLig - 1;
while (nxt >= 0 and a[iLig][col] > a[nxt][col])
nxt = up[nxt][col];
up[iLig][col] = nxt;
}
}
for (int lig = 0; lig < nbLig; ++lig) {
for (int iCol = nbCol - 1; iCol >= 0; --iCol) {
int nxt = iCol + 1;
while (nxt < nbCol and a[lig][iCol] > a[lig][nxt])
nxt = right[lig][nxt];
right[lig][iCol] = nxt;
}
for (int iCol = 0; iCol < nbCol; ++iCol) {
int nxt = iCol - 1;
while (nxt >= 0 and a[lig][iCol] > a[lig][nxt])
nxt = left[lig][nxt];
left[lig][iCol] = nxt;
}
}
int sol = 0;
for (int lig1 = 0; lig1 < nbLig; ++lig1)
for (int lig2 = lig1 + 2; lig2 < nbLig; ++lig2)
for (int col1 = 0; col1 < nbCol; ++col1)
for (int col2 = col1 + 2; col2 < nbCol; ++col2) {
bool ok = true;
for (int i = lig1 + 1; i < lig2; ++i)
ok &= right[i][col1] >= col2 and left[i][col2] <= col1;
for (int i = col1 + 1; i < col2; ++i)
ok &= up[lig2][i] <= lig1 and down[lig1][i] >= lig2;
sol += ok;
}
return sol;
}
