// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int_fast16_t INF = 7777;
const int_fast16_t LOG = 10;
const int_fast16_t N = 777;
int_fast16_t min_h[N][N], max_h[N][N], min_v[N][N], max_v[N][N];
int_fast16_t minH[N][N][LOG], maxH[N][N][LOG], minV[N][N][LOG], maxV[N][N][LOG];
__attribute__((optimize("O3,unroll-loops")))
ll count_rectangles(vector<vector<int>> a) {
int_fast16_t n = a.size(), m = a[0].size();
for (int_fast16_t i = 0; i < n; i ++) {
for (int_fast16_t j = 0; j < m; j ++) {
for (int_fast16_t ii = i; ii >= 0; ii --) {
if (a[ii][j] > a[i][j]) break;
min_v[i][j] = ii;
}
for (int_fast16_t ii = i; ii < n; ii ++) {
if (a[ii][j] > a[i][j]) break;
max_v[i][j] = ii;
}
for (int_fast16_t jj = j; jj >= 0; jj --) {
if (a[i][jj] > a[i][j]) break;
min_h[i][j] = jj;
}
for (int_fast16_t jj = j; jj < m; jj ++) {
if (a[i][jj] > a[i][j]) break;
max_h[i][j] = jj;
}
}
}
for (int_fast16_t j = 0; j < m; j ++) {
for (int_fast16_t 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_fast16_t e = 1; e < LOG; e ++) {
for (int_fast16_t j = 0; j < m; j ++) {
for (int_fast16_t 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_fast16_t u = 1; u < n - 1; u ++) {
for (int_fast16_t d = u; d < n - 1; d ++) {
int_fast16_t e = int(log2(d - u + 1));
for (int_fast16_t l = 1; l < m - 1; l ++) {
int_fast16_t mnh = INF, mxh = -INF, mnv = INF, mxv = -INF;
for (int_fast16_t r = l; r < m - 1; r ++) {
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;
}
