#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> st;

int gen(int n, int pos, vector<vector<int>> &pr_sum, bool grow = true) {
    int ans = 0;
    for (int i = 0; i < (int)st.size(); ++i) {
        ans += st[i].second - st[i].first;
    }
    if (pos == n) {
        return ans;
    }
    if (st.empty()) {
        ans = max(ans, gen(n, pos + 1, pr_sum));
    }
    auto get = [&](int i1, int j1, int i2, int j2) {
        return pr_sum[i2][j2] - pr_sum[i1][j2] - pr_sum[i2][j1] + pr_sum[i1][j1];
    };
    if (st.empty()) {
        for (int l = 0; l < n; ++l) {
            for (int r = l + 1; r <= n; ++r) {
                if (get(pos, l, pos + 1, r) == r - l) {
                    st.emplace_back(l, r);
                    ans = max(ans, gen(n, pos + 1, pr_sum));
                    st.pop_back();
                }
            }
        }
    } else {
        if (grow) {
            for (int l = 0; l < n; ++l) {
                for (int r = n; r > l; --r) {
                    if (get(pos, l, pos + 1, r) == r - l) {
                        if (l <= st.back().first && st.back().second <= r && (l == 0 || get(pos, l - 1, pos + 1, l) == 0 || r == n || get(pos, r, pos + 1, r + 1) == 0)) {
                            st.emplace_back(l, r);
                            ans = max(ans, gen(n, pos + 1, pr_sum));
                            st.pop_back();
                        }
                    }
                }
            }
        }
        bool flag = false;
        for (int l = 0; l < n; ++l) {
            for (int r = n; r > l; --r) {
                if (get(pos, l, pos + 1, r) == r - l && !flag) {
                    bool check = true;
                    for (auto [ll, rr] : st) {
                        if (!(ll <= l && r <= rr) && !(l <= ll && rr <= r)) {
                            check = false;
                            break;
                        }
                    }
                    if (l < st.back().first || st.back().second < r) {
                        check = false;
                    }
                    if (check) {
                        st.emplace_back(l, r);
                        ans = max(ans, gen(n, pos + 1, pr_sum, false));
                        st.pop_back();
                        flag = true;
                    }
                }
            }
        }
    }

    return ans;
}

int biggest_stadium(int n, vector<vector<int>> f) {
    vector<vector<int>> pr_sum(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            f[i][j] ^= 1;
            pr_sum[i + 1][j + 1] = pr_sum[i + 1][j] + pr_sum[i][j + 1] - pr_sum[i][j] + f[i][j];
        }
    }
    if (pr_sum[n][n] == n * n - 1) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!f[i][j]) {
                    return n * n - min(i + 1, n - i) * min(j + 1, n - j);
                }
            }
        }
    }
    if (n <= 30) {
        return gen(n, 0, pr_sum);
    }
    vector<vector<int>> ll(n, vector<int>(n, -1)), rr(n, vector<int>(n, n)), dd(n, vector<int>(n, n));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < n; ++j) {
            if (!f[i][j]) {
                ll[i][j] = j;
                dd[i][j] = i;
            } else {
                if (j > 0) {
                    ll[i][j] = ll[i][j - 1];
                }
                if (i + 1 < n) {
                    dd[i][j] = dd[i + 1][j];
                }
            }
        }
        for (int j = n - 1; j >= 0; --j) {
            if (!f[i][j]) {
                rr[i][j] = j;
            } else if (j + 1 < n) {
                rr[i][j] = rr[i][j + 1];
            }
        }
    }
    bool check = true;
    auto get = [&](int i1, int j1, int i2, int j2) {
        return pr_sum[i2][j2] - pr_sum[i1][j2] - pr_sum[i2][j1] + pr_sum[i1][j1];
    };
    for (int i1 = 0; i1 < n; ++i1) {
        for (int j1 = 0; j1 < n; ++j1) {
            for (int i2 = 0; i2 < n; ++i2) {
                for (int j2 = 0; j2 < n; ++j2) {
                    if (!f[i1][j1] || !f[i2][j2]) {
                        continue;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!f[i][j]) {
                continue;
            }
            int l = ll[i][j], r = rr[i][j], d = dd[i][j];
            if (get(i, 0, i + 1, l + 1) || get(d, j, n, j + 1) || get(i, r, i + 1, n)) {
                check = false;
            }
            if (l > -1 && d < n) {
                if (get(d, 0, n, l + 1)) {
                    check = false;
                }
            }
            if (r < n && d < n) {
                if (get(d, r, n, n)) {
                    check = false;
                }
            }
        }
    }
    if (check) {
        return pr_sum[n][n];
    } else {
        return pr_sum[n][n] - 1;
    }
}