#include "rect.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<short,short> pii;
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#define eb emplace_back
#define SZ(i) int(i.size())
#ifdef tmd
#define debug(...) fprintf(stderr,"%d (%s) = ",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do (T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream &printRng (IT bg, IT ed, ostream &os) {
os<<"{";
for (IT it=bg; it!=ed; it++) {
if (it!=bg) {
os<<",";
}
os<<(*it);
}
return os<<"}";
}
template<typename T> ostream &operator << (ostream &os, vector<T> &vec) {
return printRng(vec.begin(), vec.end(), os);
}
template<typename T> ostream &operator << (ostream &os, pair<T,T> &vec) {
return os<<"{"<<vec.first<<","<<vec.second<<"}";
}
template<typename T> void pary (T bg, T ed) {
printRng(bg,ed,cerr);
cerr<<endl;
}
#else
#define debug(...)
#define pary(...)
#endif // tmd
const int MAXN = 702;
int n, m;
int bit[MAXN];
void add (int x, int y) {
for (x++;x<MAXN;x+=-x&x) {
bit[x] += y;
}
}
int sqry (int x) {
int ret = 0;
for (x++;x>0; x-=-x&x) {
ret += bit[x];
}
return ret;
}
vector<vector<int> > G;
vector<pii> h[MAXN][MAXN], g[MAXN][MAXN];
int solve (int i, int j) {
vector<pair<int,int> > qry;
for (auto p : h[i][j]) {
qry.emplace_back(p.Y, p.X);
}
sort(qry.begin(), qry.end());
int res = 0;
int idx = 0;
vector<int> opr;
for (auto p : qry) {
while (idx < int(g[j][i].size()) && g[j][i][idx].X <= p.X) {
add(g[j][i][idx].Y, 1);
opr.eb(g[j][i][idx].Y);
idx++;
}
res += sqry(p.Y);
}
for (auto p : opr) {
add(p, -1);
}
return res;
}
vector<short> pa[MAXN][MAXN];
void build (vector<pii> res[MAXN][MAXN]) {
vector<int> stk;
for (int i=0; i<n; i++) {
stk.clear();
for (int j=0; j<m; j++) {
while (stk.size() && G[i][stk.back()] <= G[i][j]) {
if (stk.back() < j - 1) {
pa[stk.back()][j].eb(i);
debug(stk.back(), j, i);
}
stk.pop_back();
}
if (stk.size()) {
if (stk.back() < j - 1) {
debug(stk.back(), j, i);
pa[stk.back()][j].eb(i);
}
}
stk.eb(j);
}
}
// debug("hf");
for (int l=0; l<m; l++) {
for (int r=l+2; r<m; r++) {
int len = 0;
for (int k=SZ(pa[l][r])-1; k>=0; k--) {
if (k!=SZ(pa[l][r])-1 && pa[l][r][k]+1!=pa[l][r][k+1]) {
len = 0;
}
len++;
res[pa[l][r][k]-1][l].eb(r-l-1, len);
}
}
}
for (int i=0; i<MAXN;i++) {
for (int j=0;j<MAXN; j++) {
pa[i][j].clear();
pa[i][j].shrink_to_fit();
}
}
}
vector<vector<int> > flip (vector<vector<int> > vec) {
vector<vector<int> > res;
for (int j=0; j<SZ(vec[0]); j++) {
vector<int> cur;
for (int i=0; i<SZ(vec); i++) {
cur.emplace_back(vec[i][j]);
}
res.emplace_back(cur);
}
swap(n, m);
return res;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
G = a;
n = a.size();
m = a[0].size();
build(h);
G = flip(G);
build(g);
G = flip(G);
ll res = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
res += solve(i, j);
}
}
return res;
}
