#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int matrix[2525][2525];
int n, m;
ll div1(int s, int e){
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)+div1((s+e)/2, e);
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 solve1(){
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);
return ret;
}
ll count_rectangles(vector<vector<int>> a){
n=(int)a.size();
m=(int)a[0].size();
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) matrix[i][j]=a[i][j];
}
if (n<=3) return solve1();
return 0;
}
