#include "seats.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef int ll;
vector<pair<ll, ll>> d;
vector<ll> row, col;
set<ll> st1[1007], st2[1007];
ll n, m;
void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) {
n = h, m = w;
row.resize(h);
col.resize(w);
for(int i = h * w - 1; i >= 0; i--){
row[r[i]] = i;
col[c[i]] = i;
st1[r[i]].insert(i);
st2[c[i]].insert(i);
}
for(int i = 0; i < h * w; i++)
d.push_back({r[i], c[i]});
}
int swap_seats(int a, int b) {
st1[d[a].first].erase(a);
st2[d[a].second].erase(a);
st1[d[b].first].erase(b);
st2[d[b].second].erase(b);
swap(d[a], d[b]);
st1[d[a].first].insert(a);
st2[d[a].second].insert(a);
st1[d[b].first].insert(b);
st2[d[b].second].insert(b);
row[d[a].first] = *st1[d[a].first].begin();
col[d[a].second] = *st2[d[a].second].begin();
row[d[b].first] = *st1[d[b].first].begin();
col[d[b].second] = *st2[d[b].second].begin();
vector<pair<ll, ll>> vec1, vec2;
for(int i = 0; i < row.size(); i++)
vec1.push_back({row[i], i});
for(int i = 0; i < col.size(); i++)
vec2.push_back({col[i], i});
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
// for(auto i: vec2)
// cout << i.first << ' ' << i.second << endl;
ll mn1 = 0, mn2 = 0, mx1 = 0, mx2 = 0;
ll cur = 0;
// row col row col
ll ans = 0;
while(true){
ll p1 = mn1, p2 = mn2, p3 = mx1, p4 = mx2;
while(p1 < n && vec1[p1].second >= vec1[mn1].second)
p1++;
while(p2 < m && vec2[p2].second >= vec2[mn2].second)
p2++;
while(p3 < n && vec1[p3].second <= vec1[mx1].second)
p3++;
while(p4 < m && vec2[p4].second <= vec2[mx2].second)
p4++;
// cout << mn1 << ' ' << mn2 << ' ' << mx1 << ' ' << mx2 << endl;
// cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl;
ll next0 = n * m;
if(p1 < n)
next0 = min(next0, vec1[p1].first);
if(p2 < m)
next0 = min(next0, vec2[p2].first);
if(p3 < n)
next0 = min(next0, vec1[p3].first);
if(p4 < m)
next0 = min(next0, vec2[p4].first);
ll area = (vec1[mx1].second - vec1[mn1].second + 1) * (vec2[mx2].second - vec2[mn2].second + 1);
//cout << area << ' ' << next0 << endl;
if(area >= cur && area <= next0)
ans++;
if(next0 == vec1[p1].first)
mn1 = p1;
if(next0 == vec2[p2].first)
mn2 = p2;
if(next0 == vec1[p3].first)
mx1 = p3;
if(next0 == vec2[p4].first)
mx2 = p4;
if(p1 == n && p2 == m && p3 == n && p4 == m)
break;
}
return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/
