#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll=long long;
const ll MAX_VAL=500*1000+5,DECA=(1<<19),MODU=1000*1000*1000+7;
ll nbVal,rep;
ll multi[MAX_VAL],benef[DECA];
ll arbreMax[2*DECA],arbreProd[2*DECA];
set<ll> listeInter;
ll calcMax(ll deb,ll fin) {
if (deb==fin) {
return arbreMax[deb];
}
if (deb%2==1) {
return max(arbreMax[deb],calcMax(deb+1,fin));
}
if (fin%2==0) {
return max(arbreMax[fin],calcMax(deb,fin-1));
}
return calcMax(deb/2,fin/2);
}
ll calcProd(ll deb,ll fin) {
if (deb==fin) {
return arbreProd[deb];
}
if (deb%2==1) {
return (arbreProd[deb]*calcProd(deb+1,fin))%MODU;
}
if (fin%2==0) {
return (arbreProd[fin]*calcProd(deb,fin-1))%MODU;
}
return calcProd(deb/2,fin/2);
}
void majMax(ll pos,ll val) {
benef[pos]=val;
pos+=DECA;
arbreMax[pos]=val;
while (pos>1) {
pos/=2;
arbreMax[pos]=max(arbreMax[2*pos],arbreMax[2*pos+1]);
}
}
void majProd(ll pos,ll val) {
multi[pos]=val;
pos+=DECA;
arbreProd[pos]=val;
while (pos>1) {
pos/=2;
arbreProd[pos]=(arbreProd[2*pos]*arbreProd[2*pos+1])%MODU;
}
}
void calc() {
auto it=listeInter.end();
it--;
ll prodCour=1,meilleur=0;
while ((*it)!=-1 and prodCour*multi[(*it)]<MODU) {
prodCour*=multi[(*it)];
meilleur=max(meilleur,calcMax(DECA+(*it),DECA+nbVal-1));
meilleur*=multi[(*it)];
it--;
}
//cout<<meilleur<<" "<<max((*it),(ll)0)<<" ";
meilleur=max(meilleur,calcMax(DECA+max((*it),(ll)0),DECA+nbVal-1));
//cout<<meilleur<<endl;
if ((*it)==-1) {
ll maxi=calcMax(DECA,DECA+nbVal-1);
//cout<<meilleur<<" "<<maxi<<endl;
if (meilleur>maxi) {
rep=meilleur%MODU;
}
else {
rep=maxi;
}
}
else {
it++;
meilleur%=MODU;
if ((*it)>0) {
meilleur*=calcProd(DECA,DECA+(*it)-1);
}
rep=meilleur%MODU;
}
//cout<<rep<<endl;
}
int init(int N, int X[], int Y[]) {
nbVal=N;
for (ll i=0;i<nbVal;i++) {
multi[i]=X[i];
benef[i]=Y[i];
}
for (ll i=0;i<2*DECA;i++) {
arbreProd[i]=1;
}
for (ll i=0;i<nbVal;i++) {
arbreProd[DECA+i]=multi[i];
arbreMax[DECA+i]=benef[i];
}
for (ll i=DECA-1;i>0;i--) {
arbreProd[i]=(arbreProd[2*i]*arbreProd[2*i+1])%MODU;
arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
}
for (ll i=0;i<nbVal;i++) {
if (multi[i]>1) {
listeInter.insert(i);
}
}
listeInter.insert(-1);
//cout<<calc()<<endl;
calc();
return (int)rep;
}
int updateX(int pos, int val) {
if (multi[pos]>1) {
listeInter.erase(pos);
}
majProd(pos,val);
if (multi[pos]>1) {
listeInter.insert(pos);
}
/*for (auto i:listeInter) {
cout<<i<<" ";
}
cout<<": ";*/
calc();
return (int)rep;
}
int updateY(int pos, int val) {
majMax(pos,val);
calc();
return (int)rep;
}
