#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505;
int n, m;
vector <short> rows [maxn][maxn], cols [maxn][maxn];
vector <pair <short, short> > rows1 [maxn][maxn], cols1 [maxn][maxn];
short fenwick [maxn];
long long count_rectangles (vector <vector <int> > a){
n = a.size ();
m = a [0].size ();
if (n < 3 || m < 3) return 0;
long long ans = 0;
stack <short> s;
for (int i = n - 2; i > 0; i --){
s.push (0);
for (int j = 1; j < m; j ++){
while (!s.empty ()){
if (s.top () != j - 1) rows [s.top () + 1][j - 1].push_back (i);
if (a [i][s.top ()] < a [i][j]) s.pop ();
else{
if (a [i][s.top ()] == a [i][j]) s.pop ();
break;
}
}
s.push (j);
}
while (!s.empty()) s.pop ();
}
for (int i = m - 2; i > 0; i --){
s.push (0);
for (int j = 1; j < n; j ++){
while (!s.empty ()){
if (s.top () != j - 1) cols [s.top () + 1][j - 1].push_back (i);
if (a [s.top ()][i] < a [j][i]) s.pop ();
else{
if (a [s.top ()][i] == a [j][i]) s.pop ();
break;
}
}
s.push (j);
}
while (!s.empty()) s.pop ();
}
int sz, last, x;
for (int i = 1; i < m - 1; i ++){
for (int j = i; j < m - 1; j ++){
sz = rows [i][j].size ();
if (sz == 0) continue;
last = rows [i][j][0];
cols1 [rows [i][j][0]][i].push_back ({j, last});
for (x = 1; x < sz; x ++){
if (rows [i][j][x] < rows [i][j][x - 1] - 1) last = rows [i][j][x];
cols1 [rows [i][j][x]][i].push_back ({j, last});
}
}
}
for (int i = 1; i < n - 1; i ++){
for (int j = i; j < n - 1; j ++){
sz = cols [i][j].size ();
if (sz == 0) continue;
last = cols [i][j][0];
rows1 [i][cols [i][j][0]].push_back ({last, j});
for (x = 1; x < sz; x ++){
if (cols [i][j][x] < cols [i][j][x - 1] - 1) last = cols [i][j][x];
rows1 [i][cols [i][j][x]].push_back ({last, j});
}
}
}
int sz_r, sz_c, r, c;
for (int i = 1; i < n - 1; i ++){
for (int j = 1; j < m - 1; j ++){
sz_r = rows1 [i][j].size (), sz_c = cols1 [i][j].size ();
sort (rows1 [i][j].begin (), rows1 [i][j].end ());
r = sz_r - 1;
for (c = sz_c - 1; c >= 0; c --){
while (r >= 0 && rows1 [i][j][r].first >= cols1 [i][j][c].first){
x = rows1 [i][j][r].second;
while (x <= n){
fenwick [x] ++;
x += x & -x;
}
r --;
}
x = cols1 [i][j][c].second;
while (x > 0){
ans += fenwick [x];
x -= x & -x;
}
}
while (r < sz_r - 1){
r ++;
x = rows1 [i][j][r].second;
while (x <= n){
fenwick [x] --;
x += x & -x;
}
}
}
}
return ans;
}
//long long bruteforce (vector <vector <int> > a){
//n = a.size ();
//m = a [0].size ();
//if (n < 3 || m < 3) return 0;
//long long ans = 0;
//for (int u = 1; u < n - 1; u ++){
//for (int d = u; d < n - 1; d ++){
//for (int l = 1; l < m - 1; l ++){
//for (int r = l; r < m - 1; r ++){
//bool flag = 1;
//for (int i = u; i <= d; i ++){
//for (int j = l; j <= r; j ++){
//if (a [i][j] >= a [u - 1][j] || a [i][j] >= a [d + 1][j] || a [i][j] >= a [i][l - 1] || a [i][j] >= a [i][r + 1]){
//flag = 0;
//break;
//}
//}
//if (!flag) break;
//}
//ans += flag;
//}
//}
//}
//}
//return ans;
//}
//mt19937 mt (5172893);
//int main (){
//while (1){
//n = mt () % 5 + 1;
//m = mt () % 5 + 1;
//vector <vector <int> > a (n);
//for (int i = 0; i < n; i ++){
//for (int j = 0; j < m; j ++){
//a [i].push_back (mt () % 10);
//}
//}
//long long ans1 = count_rectangles (a);
//long long ans2 = bruteforce (a);
//if (ans1 != ans2){
//cout << "damn\n";
//cout << ans1 << ' ' << ans2 << '\n';
//cout << n << ' ' << m << '\n';
//for (auto v : a){
//for (auto i : v) cout << i << ' ';
//cout << '\n';
//}
//return 0;
//}
//cout << "ok\n";
//for (int i = 0; i <= 30; i ++){
//for (int j = 0; j <= 30; j ++){
//rows [i][j].clear ();
//cols [i][j].clear ();
//rows1 [i][j].clear ();
//cols1 [i][j].clear ();
//}
//}
//}
//}
