#include "horses.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
vector<long long> x,y;
vector<long long> st, mod, bestidx;
long long n;
const long long MOD = 1e9+7;
long long mymult(long long a, long long b){
return min((long long)1e9+3, a*b);
}
long long modmult(long long a, long long b){
return (a*b)%MOD;
}
void build(long long idx, long long left, long long right){
if(left==right){
st[idx]=x[left];
mod[idx]=x[left];
return;
}
long long mid = left + (right-left)/2;
build(2*idx,left,mid);
build(2*idx+1,mid+1,right);
st[idx]=mymult(st[2*idx],st[2*idx+1]);
mod[idx]=modmult(mod[2*idx],mod[2*idx+1]);
}
long long query1(long long idx, long long left, long long right, long long ql ,long long qr){
if(left>=ql && right<=qr){
return st[idx];
}
if(left>qr || right < ql){
return 1;
}
long long mid = left + (right-left)/2;
return mymult(query1(2*idx,left,mid,ql,qr),query1(2*idx+1,mid+1,right,ql,qr));
}
long long query2(long long idx, long long left, long long right, long long ql ,long long qr){
if(left>=ql && right<=qr){
return mod[idx];
}
if(left>qr || right < ql){
return 1;
}
long long mid = left + (right-left)/2;
return modmult(query2(2*idx,left,mid,ql,qr),query2(2*idx+1,mid+1,right,ql,qr));
}
void update(long long idx, long long left, long long right, long long pos, long long val){
if(left==right){
st[idx]=val;
mod[idx]=val;
return;
}
long long mid = left + (right-left)/2;
if(pos<=mid){
update(2*idx,left,mid,pos,val);
}
else update(2*idx+1,mid+1,right,pos,val);
st[idx]=mymult(st[2*idx],st[2*idx+1]);
mod[idx]=modmult(mod[2*idx],mod[2*idx+1]);
}
long long combine(long long f, long long s){
if(f==-1){
return s;
}
if(s==-1){
return f;
}
long long q = query1(1,1,n,f+1,s);
long long div = (y[f]+y[s]-1)/y[s];
if(div>q){
return f;
}
return s;
}
void build2(long long idx, long long left, long long right){
if(left==right){
bestidx[idx]=left;
return;
}
long long mid = left + (right-left)/2;
build2(2*idx,left,mid);
build2(2*idx+1,mid+1,right);
bestidx[idx]=combine(bestidx[2*idx],bestidx[2*idx+1]);
}
long long query3(long long idx, long long left, long long right, long long ql ,long long qr){
if(left>=ql && right<=qr){
return bestidx[idx];
}
if(left>qr || right < ql){
return -1;
}
long long mid = left + (right-left)/2;
return combine(query3(2*idx,left,mid,ql,qr),query3(2*idx+1,mid+1,right,ql,qr));
}
void update1(long long idx, long long left, long long right, long long pos, long long val){
if(left==right){
bestidx[idx]=left;
return;
}
long long mid = left + (right-left)/2;
if(pos<=mid){
update1(2*idx,left,mid,pos,val);
}
else update1(2*idx+1,mid+1,right,pos,val);
bestidx[idx]=combine(bestidx[2*idx],bestidx[2*idx+1]);
}
int init(int N, int X[], int Y[]) {
n = N;
x.resize(N+1);
y.resize(N+1);
for(int i=1; i<=N; i++){
x[i]=X[i-1];
y[i]=Y[i-1];
}
st.resize(4*N);
mod.resize(4*N);
bestidx.resize(4*N);
build(1,1,N);
build2(1,1,N);
long long bpos = bestidx[1];
return modmult(query2(1,1,n,1,bpos),y[bpos]);
}
int updateX(int pos, int val) {
pos++;
update(1,1,n,pos,val);
update1(1,1,n,pos,val);
long long bpos = bestidx[1];
return modmult(query2(1,1,n,1,bpos),y[bpos]);
}
int updateY(int pos, int val) {
pos++;
y[pos]=val;
update1(1,1,n,pos,67); // last value is junk
long long bpos = bestidx[1];
return modmult(query2(1,1,n,1,bpos),y[bpos]);
}
