#include <bits/stdc++.h>
#include "seats.h"
#define debug
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 1e6+10 ;
const int inf=1e9+10 ;
using namespace std ;
struct Rectangle
{
int r1 , c1 , r2 , c2 ;
Rectangle( int r1 = 0 , int c1 = 0 , int r2 = 0 , int c2 = 0 )
: r1(r1) , c1(c1) , r2(c2) , c2(c2) {}
} ;
int n , globalAns ;
int isRectangle[MAXN] ;
pii p[MAXN] ;
pair<pii,pii> rec[MAXN] ;
// ------------------------------------
int swap_seats(int a , int b)
{
swap(p[a] , p[b]) ;
if(b<a) swap(a,b) ;
pii p1 = ( a == 0 ? mk(inf,inf) : rec[a-1].ff ) ;
pii p2 = ( a == 0 ? mk(-1,-1) : rec[a-1].ss ) ;
lp(i,a,b+1)
{
pii cur = p[i] ;
p1 = mk( min(p1.ff,cur.ff) , min(p1.ss, cur.ss) ) ;
p2 = mk( max(p2.ff, cur.ff) , max(p2.ss, cur.ss) ) ;
rec[i] = mk(p1,p2) ;
if( (p2.ff-p1.ff+1)*(p2.ss-p1.ss+1) == i+1 )
{
if( !isRectangle[i] ) globalAns ++ ;
isRectangle[i] = 1 ;
}
else
{
if( isRectangle[i] ) globalAns -- ;
isRectangle[i] = 0 ;
}
}
return globalAns ;
}
void give_initial_chart(int h , int w , vector<int> R , vector<int> C )
{
n = R.size() ;
lp(i,0,n) p[i] = mk( R[i] , C[i] ) ;
swap_seats( 0 , n-1 ) ;
swap_seats(0,n-1) ;
}
