#include "rect.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 1000;
int n, m;
vector< vector<int> > a;
vector<pii> segC[N];
vector<int> segR[N][N];
vector<int> eqr[N];
void PrepCol(int j){
vector<int> A(n);
for(int i = 0; i < n; i++) A[i] = a[i][j];
stack<int> st;
for(int i = 0; i < n; i++){
while(!st.empty() && A[st.top()] < A[i]) st.pop();
if(!st.empty() && i - st.top() > 1)
segC[j].pb({st.top(), i});
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && A[st.top()] < A[i]) st.pop();
if(!st.empty() && st.top() - i > 1)
segC[j].pb({i, st.top()});
st.push(i);
}
sort(all(segC[j]));
segC[j].resize(unique(all(segC[j])) - segC[j].begin());
for(int i = 0; i + 1 < (int) segC[j].size(); i++){
if(segC[j][i].F < segC[j][i + 1].F && segC[j][i + 1].F < segC[j][i].S && segC[j][i].S < segC[j][i + 1].S)
assert(0);
}
// assert((segC[j][i].S <= segC[j][i + 1].S) || );
/*
cerr << "col : " << j << '\n';
for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
cerr << '\n';
*/
}
void PrepRow(int i){
vector<int> A(m);
for(int j = 0; j < m; j++) A[j] = a[i][j];
stack<int> st;
vector<pii> seg;
for(int j = 0; j < m; j++){
while(!st.empty() && A[st.top()] < A[j]) st.pop();
if(!st.empty() && j - st.top() > 1)
seg.pb({st.top(), j});
st.push(j);
}
while(!st.empty()) st.pop();
for(int j = m - 1; j >= 0; j--){
while(!st.empty() && A[st.top()] < A[j]) st.pop();
if(!st.empty() && st.top() - j > 1)
seg.pb({j, st.top()});
st.push(j);
}
sort(all(seg));
seg.resize(unique(all(seg)) - seg.begin());
/*
for(int i = 0; i + 1 < (int) seg.size(); i++)
assert(seg[i].S <= seg[i + 1].S);
*/
for(auto X : seg) segR[X.F][X.S].pb(i);
/*
cerr << "col : " << j << '\n';
for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
cerr << '\n';
*/
}
vector<int> ev[N];
vector<pii> Fen;
void Add(pii x){
Fen.pb(x);
}
void Rem(pii x){
for(int i = 0; i + 1 < (int) Fen.size(); i++){
if(Fen[i] == x) swap(Fen[i], Fen[i + 1]);
}
if(Fen.back() == x)
Fen.pop_back();
}
int Get(pii x){
int res = 0;
for(auto &y : Fen){
if(x.F <= y.F && y.S == x.S)
res ++;
}
return res;
}
ll count_rectangles(vector<vector<int> > _a){
a = _a;
n = a.size();
m = a[0].size();
cerr << "! " << n << ' ' << m << '\n';
for(int i = 1; i < m - 1; i++) PrepCol(i);
for(int i = 1; i < n - 1; i++) PrepRow(i);
//
int cnt, idx;
for(int j = m - 1; j >= 1; j--){
cnt = segC[j].size();
eqr[j].resize(cnt);
for(int i = 0; i < cnt; i++){
idx = lower_bound(all(segC[j + 1]), segC[j][i]) - segC[j + 1].begin();
eqr[j][i] = (idx == (int)segC[j + 1].size() || segC[j + 1][idx] != segC[j][i] ? 1 : eqr[j + 1][idx] + 1);
//cerr << segC[j][i].F << ", " << segC[j][i].S << " -> " << eqr[j][i] << '\n';
}
}
ll ans = 0;
for(int j1 = 1; j1 < m - 1; j1 ++){
for(int j2 = j1; j2 < m - 1; j2 ++)
ev[j2].clear();
Fen.clear();
cnt = segC[j1].size();
for(int i = 0; i < cnt; i++){
Add(segC[j1][i]);
ev[j1 + eqr[j1][i] - 1].pb(i);
}
for(int j2 = j1; j2 < m - 1; j2 ++){
vector<int> &R = segR[j1 - 1][j2 + 1];
//R.pb(-1);
int con = 1;
for(int i = 0; i < (int) R.size(); i++){
if(i == 0) con = 1;
else if(R[i] == R[i - 1] + 1) con ++;
else {
//ans += Get({R[i - 1] - con, R[i - 1] + 1});
con = 1;
}
ans += Get({R[i] - con, R[i] + 1});
}
for(auto id : ev[j2])
Rem(segC[j1][id]);
}
assert(Fen.empty());
}
return ans;
}
