#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2500 + 12;
int n, m, a[N][N], u[N][N], d[N][N], l[N][N], r[N][N];
void prec() {
	for(int i = 1; i <= n; i++) {
		vector<int> st;
		for(int j = 1; j <= m; j++) {
			while(!st.empty() && a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}
			l[i][j] = (st.empty() ? 0 : st.back());
			st.push_back(j);
		}
		st.clear();
		for(int j = m; j >= 1; j--) {
			while(!st.empty() && a[i][st.back()] <= a[i][j]) {
				st.pop_back();
			}
			r[i][j] = (st.empty() ? m + 1 : st.back());
			st.push_back(j);
		}
	}

	for(int j = 1; j <= m; j++) {
		vector<int> st;
		for(int i = 1; i <= n; i++) {
			while(!st.empty() && a[st.back()][j] <= a[i][j]) {
				st.pop_back();
			}
			u[i][j] = (st.empty() ? 0 : st.back());
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; i--) {
			while(!st.empty() && a[st.back()][j] <= a[i][j]) {
				st.pop_back();
			}
			d[i][j] = (st.empty() ? n + 1 : st.back());
			st.push_back(i);
		}
	}
	// for(int i = 1; i <= n; i++) {
	// 	for(int j = 1; j <= m; j++) {
	// 		cout << l[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
}
ll count_rectangles(vector<vector<int> > _A) {
	n = (int)_A.size();
	m = (int)_A[0].size();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = _A[i - 1][j - 1];
		}
	}
	prec();
	ll res = 0;
	for(int i = 2; i < n; i++) {
		vector<int> x(m + 1, m + 1), y(m + 1, 0);
		for(int j = i; j < n; j++) {
			for(int k = 2; k < m; k++) {
				x[k] = min(x[k], r[j][k - 1]);
				y[k] = max(y[k], l[j][k + 1]);
			}
			for(int k = 2; k < m; k++) {
				for(int f = k; f < m; f++) {
					if(d[i - 1][f] <= j || u[j + 1][f] >= i) {
						break;
					}
					// cout << i << ' ' << j << ' ' << k << ' ' << f << ' ' << x[k] << ' ' << y[f] << '\n';
					if(x[k] > f && y[f] < k) {
						res++;
					}
				}
			}
		}
	}
	return res;
}