#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
using namespace std;
vector<int> pos[2525][2525];
int n, M;
int curpossum[2525], curmax[2525];
vector<int> cur2[2525], tmp[2525];
ll div1(int s, int e, vector<vector<int>> &matrix){
if (e-s==1){
if (matrix[1][s]<matrix[1][s+1] && matrix[1][s]<matrix[1][s-1]) return 1;
return 0;
}
ll ret=div1(s, (s+e)/2, matrix)+div1((s+e)/2, e, matrix);
int x=(s+e)/2-1, y=(s+e)/2, cur;
cur=max(matrix[1][x], matrix[1][y]);
while(x>s && y<e-1){
if (cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
if (matrix[1][x-1]<matrix[1][y+1]) cur=max(cur, matrix[1][--x]);
else cur=max(cur, matrix[1][++y]);
}
if (x==s){
for (;y<=e-1;cur=max(cur, matrix[1][++y])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
}
else{
for (;x>=s;cur=max(cur, matrix[1][--x])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
}
return ret;
}
ll div1idxrev(int s, int e, int idx, vector<vector<int>> &matrix){
if (e-s==1){
if (matrix[s][idx]<matrix[s+1][idx] && matrix[s][idx]<matrix[s-1][idx] && matrix[s][idx]<min(matrix[s][idx-1], matrix[s][idx+1])) return 1;
return 0;
}
ll ret=div1idxrev(s, (s+e)/2, idx, matrix)+div1idxrev((s+e)/2, e, idx, matrix);
int x=(s+e)/2-1, y=(s+e)/2, cur;
cur=max(matrix[x][idx], matrix[y][idx]);
bool tmp1=(matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]))&&(matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]));
while(x>s && y<e-1){
if (!tmp1) return ret;
if (cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
if (matrix[x-1][idx]<matrix[y+1][idx]){
cur=max(cur, matrix[--x][idx]);
tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
}
else{
cur=max(cur, matrix[++y][idx]);
tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
}
}
if (x==s){
for (;y<=e-1;cur=max(cur, matrix[y][idx])){
if (!tmp1) return ret;
if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
y++;
tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
}
}
else{
for (;x>=s;cur=max(cur, matrix[x][idx])){
if (!tmp1) return ret;
if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
x--;
tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
}
}
return ret;
}
ll div3(int s, int e, int s0, int e0, vector<vector<int>> &matrix){
int m=(s+e)/2, m0=(s0+e0)/2;
curpossum[s]=0;
int x1=m-1, x2=m;
if (e-s==1){
ll ret=0;
for (int i=s0;i<e0;i++){
if (matrix[s][i]<matrix[s-1][i] && matrix[s][i]<matrix[s+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else curpossum[i+1]=curpossum[i];
}
for (int i=s0;i<m0;i++){
for (int &j:pos[s][i]){
if (curpossum[j+1]-curpossum[i]==(j+1-i)) ret++;
}
}
return ret;
}
ll ret=div3(s, m, s0, e0, matrix)+div3(m, e, s0, e0, matrix);
for (register int i=s0;i<e0;i++){
curmax[i]=max(matrix[x1][i], matrix[x2][i]);
if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else{
curpossum[i+1]=curpossum[i];
}
}
bool test=0;
for (register int i=s0;i<m0;i++){
cur2[i].clear();
tmp[i].clear();
register int j1=0, j2=0, sz1=pos[x1][i].size(), sz2=pos[x2][i].size();
while(j1<sz1 && j2<sz2){
if (pos[x1][i][j1]==pos[x2][i][j2]){
cur2[i].push_back(pos[x1][i][j1]);
test=1;
if (curpossum[cur2[i].back()+1]-curpossum[i]==(cur2[i].back()-i+1)){
ret++;
}
j1++, j2++;
}
else if (pos[x1][i][j1]<pos[x2][i][j2]) j1++;
else j2++;
}
}
if (!test) return ret;
while(x1>s && x2<e-1){
if (!test) return ret;
test=0;
if (matrix[x1-1][m0]<matrix[x2+1][m0] || (matrix[x1-1][m0]==matrix[x2+1][m0] && matrix[x1-1][m0-1]<matrix[x2+1][m0-1])){
x1--;
for (register int i=s0;i<e0;i++){
curmax[i]=max(curmax[i], matrix[x1][i]);
if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else{
curpossum[i+1]=curpossum[i];
}
}
for (register int i=s0;i<m0;i++){
tmp[i].clear();
register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
while(j1<sz1 && j2<sz2){
if (cur2[i][j1]==pos[x1][i][j2]){
test=1;
tmp[i].push_back(cur2[i][j1]);
if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
j1++, j2++;
}
else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
else j2++;
}
swap(tmp[i], cur2[i]);
}
}
else{
x2++;
for (register int i=s0;i<e0;i++){
curmax[i]=max(curmax[i], matrix[x2][i]);
if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else{
curpossum[i+1]=curpossum[i];
}
}
for (register int i=s0;i<m0;i++){
tmp[i].clear();
register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
while(j1<sz1 && j2<sz2){
if (cur2[i][j1]==pos[x2][i][j2]){
test=1;
tmp[i].push_back(cur2[i][j1]);
if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
j1++, j2++;
}
else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
else j2++;
}
swap(tmp[i], cur2[i]);
}
}
}
if (x1==s){
x2++;
for (;x2<=e-1;x2++){
if (!test) return ret;
test=0;
for (register int i=s0;i<e0;i++){
curmax[i]=max(curmax[i], matrix[x2][i]);
if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else{
curpossum[i+1]=curpossum[i];
}
}
for (register int i=s0;i<m0;i++){
tmp[i].clear();
register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
while(j1<sz1 && j2<sz2){
if (cur2[i][j1]==pos[x2][i][j2]){
test=1;
tmp[i].push_back(cur2[i][j1]);
if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
j1++, j2++;
}
else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
else j2++;
}
swap(tmp[i], cur2[i]);
}
}
}
else{
x1--;
for (;x1>=s;x1--){
if (!test) return ret;
for (register int i=s0;i<e0;i++){
curmax[i]=max(curmax[i], matrix[x1][i]);
if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
curpossum[i+1]=curpossum[i]+1;
}
else{
curpossum[i+1]=curpossum[i];
}
}
for (register int i=s0;i<m0;i++){
tmp[i].clear();
register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
while(j1<sz1 && j2<sz2){
if (cur2[i][j1]==pos[x1][i][j2]){
test=1;
tmp[i].push_back(cur2[i][j1]);
if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
j1++, j2++;
}
else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
else j2++;
}
swap(tmp[i], cur2[i]);
}
}
}
return ret;
}
ll div2(int s, int e, vector<vector<int>> &matrix){
if (e-s==1){
return div1idxrev(1, n-1, s, matrix);
}
int m=(s+e)/2;
ll ret=div2(s, m, matrix)+div2(m, e, matrix);
for (register int i=0;i<n;i++){
for (register int j=s;j<m;j++) pos[i][j].clear();
register int x1=m-1, x2=m, cur1=max(matrix[i][x1], matrix[i][x2]);
while(x1>s && x2<e-1){
if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
if (matrix[i][x1-1]<matrix[i][x2+1]) cur1=max(cur1, matrix[i][--x1]);
else cur1=max(cur1, matrix[i][++x2]);
}
if (x1==s){
for (;x2<=e-1;cur1=max(cur1, matrix[i][++x2])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
}
else{
for (;x1>=s;cur1=max(cur1, matrix[i][--x1])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
}
}
ret += div3(1, n-1, s, e, matrix);
return ret;
}
ll solve1(vector<vector<int>> &matrix){
if (n<=2){
return 0;
}
vector<pair<int, int>> pi;
int s=-2;
for (int i=0;i<M;i++) if (!(matrix[1][i]<matrix[0][i] && matrix[1][i]<matrix[2][i])){
if (s==-2){
s=i+1; continue;
}
if (s!=i) pi.push_back(make_pair(s, i));
s=i+1;
}
ll ret=0;
for (auto p:pi) ret += div1(p.first, p.second, matrix);
return ret;
}
ll count_rectangles(vector<vector<int>> matrix){
n=matrix.size(), M=matrix[0].size();
if (n<=3) return solve1(matrix);
else if (M<=2) return 0;
return div2(1, M-1, matrix);
}
