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

using namespace std;

namespace {

typedef long long ll;

vector<pair<int, int>> getprs(vector<int> a) {
	int n = a.size();
	vector<pair<int, int>> ret;
	vector<int> st;
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && a[st.back()] <= a[i]) {
			if (st.back() != i - 1) {
				ret.push_back({st.back(), i});
			}
			st.pop_back();
		}
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; --i) {
		while (!st.empty() && a[st.back()] <= a[i]) {
			if (st.back() != i + 1) {
				ret.push_back({i, st.back()});
			}
			st.pop_back();
		}
		st.push_back(i);
	}
	return ret;
}

const int N = 2505;

int n, m;
vector<int> rw[N][N], cl[N][N];
vector<int> up[N][N], rght[N][N];
int rwsz[N][N], clsz[N][N];

ll solve(vector<pair<int, int>> &kek, vector<pair<int, int>> &lol) {
	ll ret = 0;
	for (auto p1 : kek) {
		for (auto p2 : lol) { 
			if (p1.second >= p2.first && p2.second >= p1.first) {
				ret += 1;
			}
		}
	}
	return ret;
}

}

long long count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	for (int i = 0; i < n; ++i) {
		vector<int> a1(m);
		for (int j = 0; j < m; ++j) {
			a1[j] = a[i][j];
		}
		auto prs = getprs(a1);
		for (auto p : prs) {
			rw[i][p.first].push_back(p.second);
		}
		for (int j = 0; j < m; ++j) {
			rw[i][j].shrink_to_fit();
		}
	}
	for (int j = 0; j < m; ++j) {
		vector<int> a1(n);
		for (int i = 0; i < n; ++i) {
			a1[i] = a[i][j];
		}
		auto prs = getprs(a1);
		for (auto p : prs) {
			cl[p.first][j].push_back(p.second);
		}
		for (int i = 0; i < n; ++i) {
			cl[i][j].shrink_to_fit();
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			sort(rw[i][j].begin(), rw[i][j].end());
			rw[i][j].resize(unique(rw[i][j].begin(), rw[i][j].end()) - rw[i][j].begin());
			sort(cl[i][j].begin(), cl[i][j].end());
			cl[i][j].resize(unique(cl[i][j].begin(), cl[i][j].end()) - cl[i][j].begin());
			rw[i][j].shrink_to_fit();
			cl[i][j].shrink_to_fit();
			rwsz[i][j] = rw[i][j].size();
			clsz[i][j] = cl[i][j].size();
		}
	}
	for (int j = m - 1; j >= 0; --j) {
		for (int i = 0; i < n; ++i) {
			rght[i][j].resize(clsz[i][j]);
			for (int t = 0; t < clsz[i][j]; ++t) {
				rght[i][j][t] = 1;
				if (j != m - 1) {
					int ind = lower_bound(cl[i][j + 1].begin(), cl[i][j + 1].end(), cl[i][j][t]) - cl[i][j + 1].begin();
					if (ind != clsz[i][j + 1] && cl[i][j + 1][ind] == cl[i][j][t]) {
						rght[i][j][t] += rght[i][j + 1][ind];
					}
				}
			}
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < m; ++j) {
			up[i][j].resize(rwsz[i][j]);
			for (int t = 0; t < rwsz[i][j]; ++t) {
				up[i][j][t] = 1;
				if (i != n - 1) {
					int ind = lower_bound(rw[i + 1][j].begin(), rw[i + 1][j].end(), rw[i][j][t]) - rw[i + 1][j].begin();
					if (ind != rwsz[i + 1][j] && rw[i + 1][j][ind] == rw[i][j][t]) {
						up[i][j][t] += up[i + 1][j][ind];
					}
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			static vector<pair<int, int>> kek, lol;
			kek.clear();
			lol.clear();
			for (int rofl = 0; rofl < clsz[i - 1][j]; ++rofl) {
				kek.push_back({cl[i - 1][j][rofl] - i, rght[i - 1][j][rofl]});
			}
			for (int rofl = 0; rofl < rwsz[i][j - 1]; ++rofl) {
				lol.push_back({rw[i][j - 1][rofl] - j, up[i][j - 1][rofl]});
			}
			ans += solve(kek, lol);
		}
	}
	return ans;

}