#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
// #define debug printf
#define debug //
typedef long long ll;
const int MAXN = 2505;
vector<vector<int> > input;
int seg[4][MAXN][MAXN*4];
int mx[4][MAXN][MAXN];
int n, m;
void build(int k, int id, int sind, int ini, int fim) {
// debug("build %d %d %d %d %d\n", k, id, sind, ini, fim);
if (ini == fim) {
if (k&1) seg[k][id][sind] = mx[k][id][ini];
else seg[k][id][sind] = mx[k][ini][id];
// debug("bloh 3\n");
return;
}
int mid = (ini+fim)/2;
int e = sind*2;
int d = e+1;
build(k, id, e, ini, mid);
// debug("bloh 1\n");
build(k, id, d, mid+1, fim);
// debug("bloh 2\n");
if (k == 0 || k == 3) seg[k][id][sind] = min(seg[k][id][e], seg[k][id][d]);
else seg[k][id][sind] = max(seg[k][id][e], seg[k][id][d]);
}
int query(int k, int id, int sind, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return (k == 0 || k == 3) ? MAXN : -1;
if (ql <= l && qr >= r) return seg[k][id][sind];
int mid = (l+r)/2;
int e = sind*2;
int d = e+1;
if (k == 0 || k == 3) return min(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
return max(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
}
void precalc() {
stack<int> st;
// ------------->
for (int i = 0; i < n; i++) {
st.push(m);
for (int j = m-1; j >= 0; j--) {
while (st.top() != m && input[i][st.top()] < input[i][j]) st.pop();
mx[0][i+1][j+1] = (st.top()-1)+1;
st.push(j);
}
}
// ^^^^^^^^^^^^^
while (st.size()) st.pop();
for (int j = 0; j < m; j++) {
st.push(-1);
for (int i = 0; i < n; i++) {
while (st.top() != -1 && input[st.top()][j] < input[i][j]) st.pop();
mx[1][i+1][j+1] = (st.top()+1)+1;
st.push(i);
}
}
// <------------
while (st.size()) st.pop();
for (int i = 0; i < n; i++) {
st.push(-1);
for (int j = 0; j < m; j++) {
while (st.top() != -1 && input[i][st.top()] < input[i][j]) st.pop();
mx[2][i+1][j+1] = (st.top()+1)+1;
st.push(j);
}
}
// vvvvvvvvvvvv
while (st.size()) st.pop();
for (int j = 0; j < m; j++) {
st.push(n);
for (int i = n-1; i >= 0; i--) {
while (st.top() != n && input[st.top()][j] < input[i][j]) st.pop();
mx[3][i+1][j+1] = (st.top()-1)+1;
st.push(i);
}
}
for (int k = 0; k < 4; k++) {
debug("---k = %d---\n", k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) debug("%d ", mx[k][i][j]);
debug("\n");
}
}
for (int i = 1; i <= n; i++) {
build(1, i, 1, 1, m);
// debug("bleh\n");
build(3, i, 1, 1, m);
}
// debug("bleh2\n");
for (int i = 1; i <= m; i++) {
build(0, i, 1, 1, n);
build(2, i, 1, 1, n);
}
}
bool check(int a, int b, int c, int d) {
if (a == m || b == 1 || c == 1 || d == n) return 0;
debug("check %d %d %d %d\n", a, b, c, d);
// >>>>>>>>>>>>
int aa = query(0, c-1, 1, 1, n, b, d);
// ^^^^^^^^^^^^
int bb = query(1, d+1, 1, 1, m, c, a);
// <<<<<<<<<<<<
int cc = query(2, a+1, 1, 1, n, b, d);
// vvvvvvvvvvvv
int dd = query(3, b-1, 1, 1, m, c, a);
debug("// %d %d %d %d\n", aa, bb, cc, dd);
if (aa < a) return 0;
if (bb > b) return 0;
if (cc > c) return 0;
if (dd < d) return 0;
debug("good %d %d %d %d\n", a, b, c, d);
return 1;
}
long long count_rectangles(vector<vector<int> > INPUT) {
n = INPUT.size();
m = INPUT[0].size();
input = INPUT;
precalc();
vector<tuple<int, int, int, int> > possi;
for (int i = 2; i < n; i++) {
for (int j = 2; j < m; j++) {
int a = mx[0][i][j];
int b = mx[1][i][j];
int c = mx[2][i][j];
int d = mx[3][i][j];
possi.push_back({a, b, c, d});
}
}
sort(possi.begin(), possi.end());
auto it = unique(possi.begin(), possi.end());
possi.resize(it-possi.begin());
ll ans = 0;
for (auto rec : possi) {
int a, b, c, d;
tie(a, b, c, d) = rec;
ans += check(a, b, c, d);
}
return ans;
}
