#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int N = 710;
int a[N][N], L[N], R[N];
bitset<N> row[N][N], col[N][N];
long long 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++) a[i][j] = _a[i][j];
for(int i = 1; i < n - 1; i++) {
stack<int> st;
for(int j = 0; j < m; j++) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
L[j] = st.empty() ? 0 : st.top() + 1;
st.push(j);
}
while (!st.empty()) st.pop();
for(int j = m - 1; j >= 0; j--) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
R[j] = st.empty() ? m : st.top() - 1;
// cout << R[j] << " " << << endl;
// if (j == 0) cout << st.top() << endl;
st.push(j);
// cout << st.top() << endl;
}
for(int j = 0; j < m; j++) row[L[j]][R[j]][i] = 1;
// for(int j = m - 1; j >)
// for(int j = 0; j < m; j++) cout << a[i][j] << " ";
// for(int j = 0; j < m; j++) cout << L[j] << " " << R[j] << " " << i << endl;
cout << endl;
}
for(int j = 1; j < m - 1; j++) {
stack<int> st;
for(int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
L[i] = st.empty() ? 0 : st.top() + 1;
// if (j == 2) cout << st.size() << endl;
st.push(i);
}
while (!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
R[i] = st.empty() ? n : st.top() - 1;
st.push(i);
}
for(int i = 0; i < n; i++) col[L[i]][R[i]][j] = 1;
}
// cout << endl;
int ans = 0;
// cout << col[4][4][2] << endl;
// cout << n - 2 << endl;
for(int left = 1; left < m - 1; left++) {
for(int up = 1; up < n - 1; up++) for(int down = up; down < n - 1; down++) if (col[up][down][left]) {
// cout << up << " " << down << endl;
for(int right = left; right < m - 1 && col[up][down][right]; right++) {
bool ok = 1;
for(int j = up; j <= down && ok; j++) ok &= row[left][right][j];
if (ok) {
ans++;
// cout << up << " " << down << " " << left << " " << right << endl;
// cout << left << " " << right << " " << up << " " << down << endl;
}
}
}
}
// cout << ans;
return ans;
}
// int32_t main() {
// #define task ""
// cin.tie(0) -> sync_with_stdio(0);
// if (fopen("task.inp", "r")) {
// freopen("task.inp", "r", stdin);
// freopen("task.out", "w", stdout);
// }
// if (fopen(task".inp", "r")) {
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// }
// int n, m; cin >> n >> m;
// vector<vector<int> > _tmp;
// for(int i = 0; i < n; i++) {
// vector<int> tmp;
// for(int j = 0; j < m; j++) {
// int x; cin >> x;
// tmp.push_back(x);
// }
// _tmp.push_back(tmp);
// }
// count_rectangles(_tmp);
// }
