// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 123;
const int LOG = 10;
const int N = 777;
int min_h[N][N], max_h[N][N], min_v[N][N], max_v[N][N];
int minH[N][N][LOG], maxH[N][N][LOG], minV[N][N][LOG], maxV[N][N][LOG];
ll count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
for (int ii = i; ii >= 0; ii --) {
if (a[ii][j] > a[i][j]) break;
min_v[i][j] = ii;
}
for (int ii = i; ii < n; ii ++) {
if (a[ii][j] > a[i][j]) break;
max_v[i][j] = ii;
}
for (int jj = j; jj >= 0; jj --) {
if (a[i][jj] > a[i][j]) break;
min_h[i][j] = jj;
}
for (int jj = j; jj < m; jj ++) {
if (a[i][jj] > a[i][j]) break;
max_h[i][j] = jj;
}
}
}
for (int j = 0; j < m; j ++) {
for (int l = 0; l < n; l ++) {
minH[j][l][0] = min_h[l][j];
maxH[j][l][0] = max_h[l][j];
minV[j][l][0] = min_v[l][j];
maxV[j][l][0] = max_v[l][j];
}
}
for (int e = 1; e < LOG; e ++) {
for (int j = 0; j < m; j ++) {
for (int l = 0; l < n; l ++) {
minH[j][l][e] = min(minH[j][l][e - 1], minH[j][l + (1 << (e - 1))][e - 1]);
maxH[j][l][e] = max(maxH[j][l][e - 1], maxH[j][l + (1 << (e - 1))][e - 1]);
minV[j][l][e] = min(minV[j][l][e - 1], minV[j][l + (1 << (e - 1))][e - 1]);
maxV[j][l][e] = max(maxV[j][l][e - 1], maxV[j][l + (1 << (e - 1))][e - 1]);
}
}
}
int res = 0;
for (int u = 1; u < n - 1; u ++) {
for (int d = u; d < n - 1; d ++) {
int e = int(log2(d - u + 1));
for (int l = 1; l < m - 1; l ++) {
int mnh = INF, mxh = -INF, mnv = INF, mxv = -INF;
for (int r = l; r < m - 1; r ++) {
// mnh = min(mnh, minH[r][u][d]);
// mxh = max(mxh, maxH[r][u][d]);
// mnv = min(mnv, minV[r][u][d]);
// mxv = max(mxv, maxV[r][u][d]);
mnh = min(mnh, min(minH[r][u][e], minH[r][d - (1 << e) + 1][e]));
mxh = max(mxh, max(maxH[r][u][e], maxH[r][d - (1 << e) + 1][e]));
mnv = min(mnv, min(minV[r][u][e], minV[r][d - (1 << e) + 1][e]));
mxv = max(mxv, max(maxV[r][u][e], maxV[r][d - (1 << e) + 1][e]));
if (mnh < l) break;
if (mnv < u) break;
if (mxv > d) break;
res += (mxh == r);
}
}
}
}
return res;
}
