#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
struct rect{
int x1, y1, x2, y2;
rect() {}
rect(int a, int b, int c, int d) {
x1 = min(a, c); x2 = max(a, c);
y1 = min(b, d); y2 = max(b, d);
}
bool operator<(const rect &other) const {
if (x1 != other.x1) return x1 < other.x1;
if (y1 != other.y1) return y1 < other.y1;
if (x2 != other.x2) return x2 < other.x2;
if (y2 != other.y2) return y2 < other.y2;
return false;
}
};
using bs = bitset<700>;
ll count_rectangles(vvi a) {
int n = a.size(), m = a[0].size();
vvi gr(n, vi(m, m-1)), lr(n, vi(m, 0)), gc(n, vi(m, n-1)), lc(n, vi(m, 0));
for (int i = 0; i < n; i++) {
vi st1, st2;
for (int j = 0; j < m; j++) {
while (!st1.empty() && a[i][j] >= a[i][st1.back()]) {
gr[i][st1.back()] = j;
st1.pop_back();
}
st1.push_back(j);
}
for (int j = m-1; j >= 0; j--) {
while (!st2.empty() && a[i][j] >= a[i][st2.back()]) {
lr[i][st2.back()] = j;
st2.pop_back();
}
st2.push_back(j);
}
}
for (int j = 0; j < m; j++) {
vi st1, st2;
for (int i = 0; i < n; i++) {
while (!st1.empty() && a[i][j] >= a[st1.back()][j]) {
gc[st1.back()][j] = i;
st1.pop_back();
}
st1.push_back(i);
}
for (int i = n-1; i >= 0; i--) {
while (!st2.empty() && a[i][j] >= a[st2.back()][j]) {
lc[st2.back()][j] = i;
st2.pop_back();
}
st2.push_back(i);
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << gr[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << gc[i][j] << " ";
// }
// cout << "\n";
// }
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (gr[i][j] == m-1 && lr[i][m-1] > j) gr[i][j] = m;
if (lr[i][j] == 0 && gr[i][0] < j) lr[i][j] = -1;
if (gc[i][j] == n-1 && lc[n-1][j] > i) gc[i][j] = n;
if (lc[i][j] == 0 && gc[0][j] < i) lc[i][j] = -1;
}
}
set<rect> valid;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
int x = gr[i][j-1], y = gc[i-1][j], z = lr[i][j+1], w = lc[i+1][j];
if (x<m && y<n) { // top-left corner
bool good = (x > j) && (y > i);
// cout << "i: " << i << " j: " << j << " x: " << x << " y: " << y << "\n";
for (int k = j; k < x; k++) {
good = good && ((gc[i-1][k] == y) || (lc[y][k] == i-1));
}
for (int k = i; k < y; k++) {
good = good && ((gr[k][j-1] == x) || (lr[k][x] == j-1));
}
if (good) {
valid.insert(rect(i, j, y-1, x-1));
}
}
if (z >= 0 && y < n) { // top-right corner
bool good = (z < j) && (y > i);
for (int k = z+1; k <= j; k++) {
good = good && ((gc[i-1][k] == y) || (lc[y][k] == i-1));
}
for (int k = i; k < y; k++) {
good = good && ((lr[k][j+1] == z) || (gr[k][z] == j+1));
}
if (good) {
// cout << "i: " << i << " j: " << j << " z: " << z << " y: " << y << "\n";
valid.insert(rect(i, z+1, y-1, j));
}
}
if (x < m && w >= 0) { // bottom-left corner
bool good = (x > j) && (w < i);
for (int k = j; k < x; k++) {
good = good && ((lc[i+1][k] == w) || (gc[w][k] == i+1));
}
for (int k = w+1; k <= i; k++) {
good = good && ((gr[k][j-1] == x) || (lr[k][x] == j-1));
}
if (good) {
// cout << "i: " << i << " j: " << j << " x: " << x << " w: " << w << "\n";
valid.insert(rect(i, x-1, w+1, j));
}
}
if (z >= 0 && w >= 0) { // bottom-right corner
bool good = (z < j) && (w < i);
for (int k = z+1; k <= j; k++) {
good = good && ((lc[i+1][k] == w) || (gc[w][k] == i+1));
}
for (int k = w+1; k <= i; k++) {
good = good && ((lr[k][j+1] == z) || (gr[k][z] == j+1));
}
if (good) {
// cout << "i: " << i << " j: " << j << " z: " << z << " w: " << w << "\n";
valid.insert(rect(w+1, z+1, i, j));
}
}
}
}
// for (auto &el : valid) {
// cout << "(" << el.x1 << "," << el.y1 << ") -> " << "(" << el.x2 << "," << el.y2 << ")\n";
// }
return valid.size();
}
