#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll MOD=1e9+9ll;
set<int> s; ///skup pozicija koje nisu 1
vector<ll> sty; /// seg tree za maks za y, ali obrnut
int szy;
vector<ll> stx; /// seg tree za proizvod, ali obrnut
int szx;
vector<ll> x,y;
int stepen(int n){
int i=0;
while(1<<i < n)i++;
return (1<<i);
}
void postaviy (ll val, int pos){
pos+=szy;
sty[pos]=val;
pos/=2;
while(pos>=1){
sty[pos]=max(sty[pos*2],sty[pos*2+1]);
pos/=2;
}
}
ll gety (int l, int r){
l+=szy;
r+=szy;
int ans=0ll;
while(l<=r){
if(l%2==1)ans=(ll)max((int)ans,(int)sty[l++]);
if(r%2==0)ans=(ll)max((int)ans,(int)sty[r--]);
l/=2;
r/=2;
}
return ans;
}
void postavix (ll val, int pos){
pos+=szx;
stx[pos]=val;
pos/=2;
while(pos>=1){
stx[pos]=(stx[pos*2]*stx[pos*2+1])%MOD;;
pos/=2;
}
}
ll getx (int l, int r){
l+=szx;
r+=szx;
ll ans=1ll;
while(l<=r){
if(l%2==1)ans=(ans*stx[l++])%MOD;
if(r%2==0)ans=(ans*stx[r--])%MOD;
l/=2;
r/=2;
}
return (ans%MOD);
}
ll resi(){
ll ans=1ll;
int cur=0;
//for(int i=0;i<stx.size();i++)cout<<stx[i]<<' ';
//cout<<endl;
//for(int i=0;i<sty.size();i++)cout<<sty[i]<<' ';
//cout<<endl;
//for(auto a:s)cout<<a<<' ';
//cout<<endl;
bool ok=false;
for(auto a:s){
if(ans>MOD){
ans%=MOD;
ok=true;
break;
}
ans=x[n-a-1]*max(ans,gety(cur,a));
cur=a+1;
}
ans=(ans*getx(cur,n-1))%MOD;
if(!ok)ans=max(ans,gety(cur,n-1));
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
x.resize(n);
for(int i=0;i<n;i++)x[i]=(ll)X[i];
y.resize(n);
for(int i=0;i<n;i++)y[i]=(ll)Y[i];
for(int i=0;i<n;i++){
if(X[i]!=1)
s.insert(n-i-1);
}
szy=stepen(n);
sty.assign(2*szy,0ll);
for(int i=0;i<n;i++)postaviy((ll)Y[i],n-i-1);
szx=stepen(n);
stx.assign(2*szx,1ll);
for(int i=0;i<n;i++)postavix((ll)X[i],n-i-1);
return (int)resi();
}
int updateX(int pos, int val) {
if(x[pos]!=1ll)s.erase(n-pos-1);
x[pos]=val;
postavix((ll)val, n-pos-1);
if(val!=1)s.insert(n-pos-1);
return resi();
}
int updateY(int pos, int val) {
y[pos]=val;
postaviy((ll)val,n-pos-1);
return resi();
}
