#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
vector<vector<int>>a;
int n, m;
namespace sub123{
bool check(int x, int y, int u, int v){
for(int i = x; i <= u; i++){
for(int j = y; j <= v; j++){
if(a[i][j] >= min(min(a[x - 1][j], a[u + 1][j]), min(a[i][y - 1], a[i][v + 1]))){
return false;
}
}
}
return true;
}
ll solve(){
int ans = 0;
for(int x = 1; x < n; x++){
for(int y = 1; y < m; y++){
for(int u = x; u + 1 < n; u++){
for(int v = y; v + 1 < m; v++){
if(check(x, y, u, v)){
ans++;
}
}
}
}
}
return ans;
}
}
namespace sub4{
const int lim = 702;
int bit[lim], mxv[lim], bd[lim], bu[lim], rbd[lim], rbu[lim], up[lim][lim], down[lim][lim];
bitset<lim>can;
vector<int>query[lim];
void update(int p){
for(p++; p < lim; p += p & -p){
bit[p]++;
}
}
int get(int p){
int ans = 0;
for(p++; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
ll solve(){
for(int j = 0; j < m; j++){
vector<int>st;
for(int i = 0; i < n; st.push_back(i++)){
while(!st.empty() && a[st.back()][j] < a[i][j]){
st.pop_back();
}
up[i][j] = (st.empty() ? 0 : st.back());
}
st.clear();
for(int i = n - 1; i > -1; st.push_back(i--)){
while(!st.empty() && a[st.back()][j] < a[i][j]){
st.pop_back();
}
down[i][j] = (st.empty() ? n - 1 : st.back());
}
}
ll ans = 0;
for(int l = 1; l < m; l++){
for(int i = 0; i < n; i++){
mxv[i] = bu[i] = can[i] = 0;
}
fill(bd, bd + n, n - 1);
for(int r = l; r + 1 < m; r++){
for(int i = 0; i < n; i++){
maximize(mxv[i], a[i][r]);
minimize(bd[i], down[i][r]);
maximize(bu[i], up[i][r]);
can[i] = mxv[i] < min(a[i][l - 1], a[i][r + 1]);
}
rbd[n - 1] = bd[n - 1];
for(int i = n - 2; i > -1; i--){
rbd[i] = !can[i + 1] ? i + 1 : rbd[i + 1];
}
for(int i = n - 2; i > -1; i--){
query[min(rbd[i], bd[i])].push_back(i);
}
rbu[0] = bu[0];
for(int i = 1; i < n; i++){
rbu[i] = !can[i - 1] ? i - 1 : rbu[i - 1];
}
memset(bit, 0, sizeof(bit));
for(int i = 1; i < n; i++){
update(max(bu[i], rbu[i]));
for(int& j : query[i]){
ans += get(j) - j - 1;
}
query[i].clear();
}
}
}
return ans;
}
}
namespace sub5{
ll solve(){
int ans = 0;
for(int l = 1; l < m; l++){
for(int r = l, mv = 0; r + 1 < m; r++){
maximize(mv, a[1][r]);
if(a[1][r] >= min(a[0][r], a[2][r]) || mv >= a[1][l - 1]){
break;
}
if(mv < a[1][r + 1]){
ans++;
}
}
}
return ans;
}
}
const int INF = 1e9;
namespace sub6{
bool check_subtask(){
for(int i = 0; i < n; i++){
if(*max_element(a[i].begin(), a[i].end()) > 1){
return false;
}
}
return true;
}
int cnt, min_x, max_x, min_y, max_y;
void dfs(int x, int y){
if(x < 0 || x >= n || y < 0 || y >= m || a[x][y] == 1){
return;
}
cnt++;
a[x][y] = 1;
minimize(min_x, x);
maximize(max_x, x);
minimize(min_y, y);
maximize(max_y, y);
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
ll solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(a[i][j] == 0){
cnt = max_x = max_y = 0;
min_x = min_y = INF;
dfs(i, j);
if(min_x > 0 && max_x + 1 < n && min_y > 0 && max_y + 1 < m && cnt == (max_x - min_x + 1) * (max_y - min_y + 1)){
ans++;
}
}
}
}
return ans;
}
}
namespace sub7{
const int lim = 2505;
int bit[lim], beg[lim][lim], lst[lim][lim];
vector<pair<int, int>>row[lim][lim], col[lim][lim];
void update(int p, int x){
for(p++; p < lim; p += p & -p){
bit[p] += x;
}
}
int get(int p){
int ans = 0;
for(p++; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
ll solve(){
memset(lst, 0x3f, sizeof(lst));
for(int i = 0; i < n; i++){
vector<int>st;
for(int j = 0; j < m; st.push_back(j++)){
while(!st.empty() && a[i][st.back()] <= a[i][j]){
if(st.size() > 1 && a[i][st.back()] < a[i][j]){
int l = st[int(st.size()) - 2] + 1, r = j - 1;
if(lst[l][r] + 1 != i){
beg[l][r] = i;
}
row[lst[l][r] = i][r].push_back(make_pair(beg[l][r], l));
}
st.pop_back();
}
}
}
memset(lst, 0x3f, sizeof(lst));
for(int j = 0; j < m; j++){
vector<int>st;
for(int i = 0; i < n; st.push_back(i++)){
while(!st.empty() && a[st.back()][j] <= a[i][j]){
if(st.size() > 1 && a[st.back()][j] < a[i][j]){
int l = st[int(st.size()) - 2] + 1, r = i - 1;
if(lst[l][r] + 1 != j){
beg[l][r] = j;
}
col[r][lst[l][r] = j].push_back(make_pair(l, beg[l][r]));
}
st.pop_back();
}
}
}
ll ans = 0;
memset(bit, 0, sizeof(bit));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
sort(row[i][j].begin(), row[i][j].end(), greater<pair<int, int>>());
sort(col[i][j].begin(), col[i][j].end(), greater<pair<int, int>>());
int p = 0;
for(auto& [r1, c1] : row[i][j]){
while(p < col[i][j].size() && col[i][j][p].first >= r1){
update(col[i][j][p++].second, 1);
}
ans += get(c1);
}
while(p-- > 0){
update(col[i][j][p].second, -1);
}
}
}
return ans;
}
}
ll count_rectangles(vector<vector<int>>_a){
swap(a, _a);
if(min(n = a.size(), m = a[0].size()) < 3){
return 0;
}
if(max(n = a.size(), m = a[0].size()) <= 200){
return sub123::solve();
}
if(n == 3){
return sub5::solve();
}
if(max(n, m) <= 700){
return sub4::solve();
}
if(sub6::check_subtask()){
return sub6::solve();
}
return sub7::solve();
}
