#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,bool> lb;
int n;
const ll big=1000000007;
lb seg_x[2000040];
int seg_m[2000040];
ll y[500010];
int pos[500010];
int inte[2000040][2];
void build_x(int X[],int v,int st,int ed)
{
inte[v][0]=st;
inte[v][1]=ed;
if(st==ed)
{
pos[st]=v;
seg_x[v]={((ll)X[st])%big,((ll)X[st])>=big};
return;
}
int mid=(st+ed)>>1;
build_x(X,2*v,st,mid);
build_x(X,2*v+1,mid+1,ed);
ll temp=seg_x[2*v].first*seg_x[2*v+1].first;
seg_x[v]={temp%big,(temp>=big || seg_x[2*v].second || seg_x[2*v+1].second)};
}
lb ti(lb a,lb b)
{
ll temp=a.first*b.first;
return {(temp%big),temp>=big || a.second || b.second};
}
lb prod(int st,int ed,int v)
{
if(st==inte[v][0] && ed==inte[v][1]) return seg_x[v];
int mid=(inte[v][0]+inte[v][1])>>1;
if(ed<=mid) return prod(st,ed,2*v);
if(st>mid) return prod(st,ed,2*v+1);
return ti(prod(st,mid,2*v),prod(mid+1,ed,2*v+1));
}
void build_m(int v,int st,int ed)
{
if(st==ed)
{
seg_m[v]=st;
return;
}
int mid=(st+ed)>>1;
build_m(2*v,st,mid);
build_m(2*v+1,mid+1,ed);
int a=seg_m[2*v],b=seg_m[2*v+1];
lb temp=prod(a+1,b,1);
if(temp.second || temp.first*y[b]>=y[a]) seg_m[v]=b;
else seg_m[v]=a;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++) y[i]=Y[i];
build_x(X,1,0,n-1);
build_m(1,0,n-1);
int temp=seg_m[1];
return (int)((prod(0,temp,1).first*y[temp])%big);
}
void change(int p)
{
int v=pos[p];
v>>=1;
int a,b;
lb temp;
while(v)
{
a=seg_m[2*v];
b=seg_m[2*v+1];
temp=prod(a+1,b,1);
if(temp.second || temp.first*y[b]>=y[a]) seg_m[v]=b;
else seg_m[v]=a;
v>>=1;
}
}
int updateX(int p, int val) {
int v=pos[p];
seg_x[v]={((ll)val)%big,((ll)val)>=big};
v>>=1;
ll temp;
while(v)
{
temp=seg_x[2*v].first*seg_x[2*v+1].first;
seg_x[v]={temp%big,(temp>=big || seg_x[2*v].second || seg_x[2*v+1].second)};
v>>=1;
}
change(p);
int temp2=seg_m[1];
return (int)((prod(0,temp2,1).first*y[temp2])%big);
}
int updateY(int p, int val) {
y[p]=val;
change(p);
int temp2=seg_m[1];
return (int)((prod(0,temp2,1).first*y[temp2])%big);
}
