#include "cross.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> arr[200005];
ll it[800005], ot[800005];
int n;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
ll update(ll st[], int idx, ll v, int p, int x, int y)
{
if(idx<x || idx>y) return st[p];
if(x==y) return st[p]=v;
int mid=x+y>>1;
return st[p]=min(update(st, idx, v, p<<1, x, mid), update(st, idx, v, (p<<1)+1, mid+1, y));
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O)
{
n=I.size();
memset(it, 0x3f, sizeof(it));
memset(ot, 0x3f, sizeof(ot));
for(int i=0; i<n; i++)
{
arr[i]={O[i], I[i]};
}
sort(arr, arr+n);
for(int i=0; i<K; i++)
{
update(ot, i, arr[i].first, 1, 0, n);
update(it, i, arr[i].second, 1, 0, n);
}
ll ans=0;
for(int i=0; i<n; i++)
{
ll isize=it[1], osize=ot[1];
ans=max(ans, osize*osize-(osize-isize)*(osize-isize));
// cout<<ans<<' ';
update(ot, i, INF, 1, 0, n);
update(it, i, INF, 1, 0, n);
update(ot, (i+K)%n, arr[(i+K)%n].first, 1, 0, n);
update(it, (i+K)%n, arr[(i+K)%n].second, 1, 0, n);
}
return ans;
}
