#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 2048; const ll E = 11; const ll INF = 1e7;
ll N;
ll ans = 0;
ll stt[Nm][2*Nm]; //y, x-segtree (coordinate of closest top point)
ll stb[Nm][2*Nm]; //same but bottom
ll nxtr[Nm][Nm];
map<ll,ll> m0[Nm+1]; //m0[top-bottom][COORDINATE COMPRESSION]->value
//COORD COMPR: (left)<<33+(right)<<22+(top)<<11+bottom
inline ll v2(ll x) {
return __builtin_ctz(x);
}
ll gtb(ll xl, ll xr, ll y0) {
if (xl>xr) {
return -1;
}
ll vl = v2(xl); ll vr = v2(xr+1);
if (vl<vr) {
return max(stb[y0][(xl>>vl)+(1<<(E-vl))],gtb(xl+(1<<vl),xr,y0));
} else {
return max(stb[y0][(xr>>vr)+(1<<(E-vr))],gtb(xl,xr-(1<<vr),y0));
}
}
ll gtt(ll xl, ll xr, ll y0) {
if (xl>xr) {
return N;
}
ll vl = v2(xl); ll vr = v2(xr+1);
if (vl<vr) {
return min(stt[y0][(xl>>vl)+(1<<(E-vl))],gtt(xl+(1<<vl),xr,y0));
} else {
return min(stt[y0][(xr>>vr)+(1<<(E-vr))],gtt(xl,xr-(1<<vr),y0));
}
}
pii gt(ll xl, ll xr, ll y0) {
pii gtp ={gtb(xl,xr,y0),gtt(xl,xr,y0)};
//cerr << "xl="<<xl<<",xr="<<xr<<",y0="<<y0<<"; gtp="<<gtp.first<<","<<gtp.second<<"\n";
assert(gtp.second>=gtp.first);
//exit(0);
return gtp;
}
ll biggest_stadium(int _N, vector<vector<int>> F) {
N = _N;
//cout << "N="<<N<<"\n";
for (ll i=0;i<N;i++) { //view as coordinates (j,i), screw original system
for (ll j=0;j<N;j++) {
if (F[i][j]==1) {
stt[i][j+Nm]=i;
stb[i][j+Nm]=i;
} else {
stt[i][j+Nm]=N;
stb[i][j+Nm]=-1;
}
if (i>=1) {
stb[i][j+Nm]=max(stb[i][j+Nm],stb[i-1][j+Nm]);
}
}
ll nval = N;
for (ll j=(N-1);j>=0;j--) {
if (F[i][j]==1) {
nval = j;
}
nxtr[i][j]=nval;
}
}
for (ll i=(N-2);i>=0;i--) {
for (ll j=0;j<N;j++) {
stt[i][j+Nm]=min(stt[i][j+Nm],stt[i+1][j+Nm]);
}
}
for (ll i=0;i<N;i++) {
for (ll j=(Nm-1);j>=1;j--) {
stt[i][j]=min(stt[i][2*j],stt[i][2*j+1]);
stb[i][j]=max(stb[i][2*j],stb[i][2*j+1]);
}
}
for (ll i=0;i<N;i++) {
ll rj = N-1;
for (ll j=(N-1);j>=-1;j--) {
if (j==-1 || F[i][j]==1) {
if (rj>j) {
pii ph = gt(j+1,rj,i);
ph.first++; ph.second--;
if (ph.second>=ph.first) {
//cout << "new box1: "<<(j+1)<<","<<(rj)<<","<<(ph.second)<<","<<ph.first<<"\n";
m0[ph.second-ph.first][((j+1)<<33)+(rj<<22)+(ph.second<<11)+(ph.first)]=(ph.second-ph.first+1)*(rj-j);
}
rj = j;
}
}
}
}
//exit(0);
for (ll H0=0;H0<=N;H0++) {
for (pii PT: m0[H0]) {
ll MSK = PT.first; ll VAL = PT.second;
ans = max(ans,VAL);
ll xl = (MSK>>33)&(2047);
ll xr = (MSK>>22)&(2047);
ll yr = (MSK>>11)&(2047);
ll yl = (MSK)&(2047);
//cout << "process xl,xr,yl,yr="<<xl<<","<<xr<<","<<yl<<","<<yr<<"\n";
if (yr<(N-1)) {
ll xc = xl;
ll xn = xl;
while (xc <= xr) {
xn = nxtr[yr+1][xc];
if (xn>xr) {
xn = xr+1;
}
if (xc<xn) {
pii ph = gt(xc,xn-1,yr+1);
ph.second--; ph.first++;
if ((ph.second-ph.first)>H0) {
//cout << "new box2: "<<(xc)<<","<<(xn-1)<<","<<(ph.second)<<","<<(ph.first)<<"\n";
m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=max(m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)],VAL+(ph.second-ph.first+1)*(xn-xc)-(yr-yl+1)*(xn-xc));
}
}
xc = xn+1;
}
}
if (yl>0) {
ll xc = xl;
ll xn = xl;
while (xc <= xr) {
xn = nxtr[yl-1][xc];
if (xn>xr) {
xn = xr+1;
}
if (xc<xn) {
pii ph = gt(xc,xn-1,yl-1);
ph.second--; ph.first++;
if ((ph.second-ph.first)>H0) {
//cout << "new box3: "<<(xc)<<","<<(xn-1)<<","<<(ph.second)<<","<<(ph.first)<<"\n";
m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=max(m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)],VAL+(ph.second-ph.first+1)*(xn-xc)-(yr-yl+1)*(xn-xc));
}
}
xc = xn+1;
}
}
}
}
return ans;
}
