#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
int ans=n*m, l=1, r=n*m;
while (l<=r) {
int mid=(l+r)/2;
vector<vector<int>> x(n, vector<int>(m, 0));
for (int i=0; i<n; i++) {
queue<int> q;
for (int j=m-1; j>=0; j--) {
if (a[i][j]<=mid) q.push(j);
if (!q.empty() && q.front()-j>=w) q.pop();
x[i][j]=(int)q.size();
}
}
int res=0;
for (int j=0; j<m; j++) {
int sum=0;
for (int i=n-1; i>=0; i--) {
if (i+h<n) sum-=x[i+h][j];
sum+=x[i][j];
res=max(res, sum);
}
}
if (res>(h*w/2)) ans=mid, r=mid-1;
else l=mid+1;
}
return ans;
}
