#include <bits/stdc++.h>
#include "quality.h"
#define MAX 11000000
typedef std::pair<int,int> pii;
#define MINM 3005
pii vals[MAX];
int matriz[MINM][MINM]={};
int getval(int x,int y){
if(x<0||y<0)return 0;
return matriz[x][y];
}
int getrectangle(int x1,int y1,int x2,int y2){
return getval(x2,y2) + getval(x1-1,y1-1) - getval(x2,y1-1) - getval(x1-1,y2);
}
bool tentar(int p,int N,int M,int H,int W){
memset(matriz,0,sizeof(matriz));
// std::cout<<"Processando "<<p<<"\n";
for(int i=0;i!=p;++i){
auto z = vals[i];
// std::cout<<"Add "<<z.first<<" "<<z.second<<"\n";
matriz[z.first][z.second]++;
}
for(int i=0;i!=MINM-3;++i){
int s=0;
for(int j=0;j!=MINM-3;++j){
s+=matriz[i][j];
matriz[i][j]=s;
if(i)
matriz[i][j]+=matriz[i-1][j];
}
}
int precisa = (H*W)/2;
/* for(int i=0;i!=N;++i){
for(int j=0;j!=M;++j)
std::cout<<matriz[i][j]<<" ";
std::cout<<"\n";
}
std::cout<<"\n";*/
for(int i=0;i!=N;++i){
for(int j=0;j!=M;++j){
int x2=i+H-1,y2=j+W-1;
if(x2>=N||y2>=M)continue;
int x = getrectangle(i,j,x2,y2);
if(x>precisa)return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
for(int i=0;i!=R;++i){
for(int j=0;j!=C;++j){
vals[Q[i][j]-1]={i,j};
}
}
int la=0,ra=R*C;
while(la<ra){
int m = (la+ra)/2;
if(tentar(m,R,C,H,W)){
ra=m;
}else la=m+1;
}
return la;
}
