#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2505
#define LOGN 12
vector<pii> rng_h[MAXN], rng_v[MAXN];
vector<int> hor[MAXN][MAXN], ver[MAXN][MAXN];
vector<int> nxt_hor[MAXN][MAXN], nxt_ver[MAXN][MAXN];
void compute(vector<vector<int>> &a, int t){
int n = a.size(), m = a.front().size();
if (t == 1) swap(n, m);
for (int i = 1; i < n - 1; i++){
set<int> s;
vector<int> v(m);
iota(v.begin(), v.end(), 0);
sort(v.begin(), v.end(), [&](int x, int y){
if (t == 0){
if (a[i][x] == a[i][y]) return x < y;
return a[i][x] > a[i][y];
}
else{
if (a[x][i] == a[y][i]) return x < y;
return a[x][i] > a[y][i];
}
});
int it = 0;
while(it < m){
vector<int> tmp;
int last = 0;
if (t) last = a[v[it]][i];
else last = a[i][v[it]];
while(it < m){
if (t == 0 && a[i][v[it]] != last) break;
else if (t == 1 && a[v[it]][i] != last) break;
tmp.pb(v[it]);
it++;
}
for (int j = 0; j < tmp.size(); j++){
int x = tmp[j];
auto it2 = s.lower_bound(x);
int prv = -1, nxt = m + 1;
if (j > 0) prv = tmp[j - 1];
if (j + 1 < tmp.size()) nxt = tmp[j + 1];
if (it2 != s.begin() && !s.empty()){
it2--;
if (x - 1 > *it2) {
if (t == 0) rng_h[i].pb({*it2 + 1, x - 1});
else rng_v[i].pb({*it2 + 1, x - 1});
}
}
it2 = s.lower_bound(x);
if (it2 != s.end()){
if (*it2 > x + 1 && *it2 < nxt) {
if (t == 0) rng_h[i].pb({x + 1, *it2 - 1});
else rng_v[i].pb({x + 1, *it2 - 1});
}
}
s.insert(x);
}
}
}
}
int b_search(vector<int> &v, int pos){
int ans = pos;
for (int i = LOGN; i >= 0; i--){
int tmp = ans + (1<<i);
if (tmp >= v.size()) continue;
if (v[tmp] - v[pos] == tmp - pos) ans = tmp;
}
return ans;
}
long long count_rectangles(vector<vector<int>> a){
compute(a, 0);
compute(a, 1);
int n = a.size(), m = a.front().size();
for (int i = 1; i < n - 1; i++){
sort(rng_h[i].begin(), rng_h[i].end());
for (auto j : rng_h[i]){
hor[j.st][j.nd].pb(i);
}
}
for (int i = 1; i < m - 1; i++){
sort(rng_v[i].begin(), rng_v[i].end());
for (auto j : rng_v[i]){
ver[j.st][j.nd].pb(i);
}
}
for (int i = 1; i < n - 1; i++){
for (int j = i; j < n - 1; j++){
int k = ver[i][j].size();
nxt_ver[i][j].resize(k, 0);
iota(nxt_ver[i][j].begin(), nxt_ver[i][j].end(), 0);
for (int l = k - 2; l >= 0; l--){
if (ver[i][j][l] + 1 == ver[i][j][l + 1]) nxt_ver[i][j][l] = nxt_ver[i][j][l + 1];
}
}
}
for (int i = 1; i < m - 1; i++){
for (int j = i; j < m - 1; j++){
int k = hor[i][j].size();
nxt_hor[i][j].resize(k, 0);
iota(nxt_hor[i][j].begin(), nxt_hor[i][j].end(), 0);
for (int l = k - 2; l >= 0; l--){
if (hor[i][j][l] + 1 == hor[i][j][l + 1]) nxt_hor[i][j][l] = nxt_hor[i][j][l + 1];
}
}
}
long long ans = 0;
for (int i = 1; i < n - 1; i++){
for (int j = 1; j < m - 1; j++){
vector<pii> horr, verr;
int pos = lower_bound(rng_h[i].begin(), rng_h[i].end(), make_pair(j, 0)) - rng_h[i].begin();
while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
int l = j, r = rng_h[i][pos].nd;
pos++;
int curr = lower_bound(hor[l][r].begin(), hor[l][r].end(), i) - hor[l][r].begin();
int to = hor[l][r][nxt_hor[l][r][curr]];
horr.pb({r, to});
}
pos = lower_bound(rng_v[j].begin(), rng_v[j].end(), make_pair(i, 0)) - rng_v[j].begin();
while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
int l = i, r = rng_v[j][pos].nd;
pos++;
int curr = lower_bound(ver[l][r].begin(), ver[l][r].end(), j) - ver[l][r].begin();
int to = ver[l][r][nxt_ver[l][r][curr]];
verr.pb({r, to});
}
for (auto k : horr){
for (auto l : verr)
if (l.nd >= k.st && k.nd >= l.st) ans++;
}
}
}
return ans;
return 0;
}
/*
int main() {
fileio();
int n, m;
cin>>n>>m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>a[i][j];
}
}
long long result = count_rectangles(a);
printf("%lld\n", result);
return 0;
}*/
