#include "horses.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define debug(a) cerr << #a << ": " << a << "\n";
#define maxc 1000000000ll
#define ssize(x) (int(x.size()))
#define mod 1000000007ll
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
struct prz_ilo{
int N;
vector<ll> drz;
void inicjalizuj(vector<ll> vec){
int n = ssize(vec);
for(N = 1; N < n;) N <<= 1;
drz.resize(N<<1, 1ll);
REP(i, n) drz[N+i] = vec[i];
for(int i = N; --i;) drz[i] = (drz[i<<1]*drz[i<<1|1])%mod;
}
ll wart(int poz){
return drz[N+poz];
}
void ustaw(int poz, ll wart){
for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = (drz[poz<<1]*drz[poz<<1|1])%mod;
}
ll ilo(int p, int k){
ll ret = 1ll;
for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
if(p&1) ret = (ret*drz[p++])%mod;
if(k&1) ret = (ret*drz[--k])%mod;
}
return ret;
}
} prz_ilo;// na ciagu x
struct prz_maks{
int N;
vector<ll> drz;
void inicjalizuj(vector<ll> vec){
int n = ssize(vec);
for(N = 1; N < n;) N <<= 1;
drz.resize(N<<1, 0ll);
REP(i, n) drz[N+i] = vec[i];
for(int i = N; --i;) drz[i] = max(drz[i<<1], drz[i<<1|1]);
}
ll wart(int poz){
return drz[N+poz];
}
void ustaw(int poz, ll wart){
for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = max(drz[poz<<1], drz[poz<<1|1]);
}
ll maks(int p, int k){
ll ret = 0ll;
for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
if(p&1) ret = max(ret, drz[p++]);
if(k&1) ret = max(ret, drz[--k]);
}
return ret;
}
} prz_maks;// na ciagu y
int n;
set<int> nie1;// pozycje nie1 w ciagu x, ale pozycja 0 zawsze jest
int wynik(){
ll wyn = -1ll, musze = -1ll;
for(auto it = prev(nie1.end()); 1; it = prev(it)){
if(musze > maxc) break;
ll maks = prz_maks.maks(*it, n-1);
if(maks > musze) wyn = (prz_ilo.ilo(0, *it)*maks)%mod, musze = maks;
musze *= prz_ilo.wart(*it);
if(it == nie1.begin()) break;
}
return wyn;
}
int init(int nn, int xint[], int yint[]){
n = nn;
vector<ll> x(n), y(n);
REP(i, n) x[i] = xint[i], y[i] = yint[i];
/*ll wyn = 0ll;
REP(i, n){
ll tmp = y[i];
FOR(j, 0, i) tmp *= x[j];
wyn = max(wyn, tmp);
}
return wyn;*/
prz_ilo.inicjalizuj(x);
prz_maks.inicjalizuj(y);
vector<int> vecnie1;
REP(i, n) if(!i || x[i] > 1ll) vecnie1.emplace_back(i);
nie1 = set<int>(all(vecnie1));
return wynik();
}
int updateX(int poz, int wart){
prz_ilo.ustaw(poz, wart);
if(!poz || wart > 1) nie1.emplace(poz);
else nie1.erase(poz);
return wynik();
}
int updateY(int poz, int wart){
prz_maks.ustaw(poz, wart);
return wynik();
}
