#include "horses.h"
#include<bits/stdc++.h>
#define ll(x) x*2+1
#define rr(x) x*2+2
#define eps 1e-9
using namespace std;
typedef long long i64;
int mod = 1e9 + 7;
// vector<i64> st;
vector<double> st_inv;
vector<int> st_max;
vector<int> x, y;
int n;
void build_inv(int l, int r, int node){
if(l == r){
st_inv[node] = 1.0 / ((double) x[l]);
return ;
}
int mid = (l + r) >> 1;
build_inv(l, mid, ll(node));
build_inv(mid + 1, r, rr(node));
st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
void update_inv(int pos, int l, int r, int node){
if(l == r){
st_inv[node] = 1.0 / ((double) x[l]);
return ;
}
int mid = (l + r) >> 1;
if(pos <= mid) update_inv(pos, l, mid, ll(node));
else update_inv(pos, mid + 1, r, rr(node));
st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
double query_inv(int ql, int qr, int l, int r, int node){
if(qr < l || r < ql) return 1.0;
if(ql <= l && r <= qr) return st_inv[node];
int mid = (l + r) >> 1;
return query_inv(ql, qr, l, mid, ll(node)) * query_inv(ql, qr, mid + 1, r, rr(node));
}
double query_inv(int ql, int qr){
return query_inv(ql, qr, 0, n - 1, 0);
}
void build_max(int l, int r, int node){
if(l == r){
st_max[node] = l;
return ;
}
int mid = (l + r) >> 1;
build_max(l, mid, ll(node));
build_max(mid + 1, r, rr(node));
int li = st_max[ll(node)], ri = st_max[rr(node)];
double inv = query_inv(li + 1, ri);
double haritsa = ((double) y[ri]) / ((double) y[li]);
if(haritsa >= inv) st_max[node] = ri;
else st_max[node] = li;
}
// void update_max(int pos, int l, int r, int node){
// if(pos < l || r < pos) return ;
// if(l == r){
// st_max[node] = l;
// return ;
// }
// int mid = (l + r) >> 1;
// update_max(l, mid, ll(node));
// update_max(mid + 1, r, rr(node));
// int li = st_max[ll(node)], ri = st_max[rr(node)];
// double inv = query_inv(li + 1, ri);
// double haritsa = ((double) y[ri]) / ((double) y[li]);
// if(haritsa >= inv) st_max[node] = ri;
// else st_max[node] = li;
// }
int query_max(int ql, int qr, int l, int r, int node){
if(qr < l || r < ql) return -1;
if(ql <= l && r <= qr) return st_max[node];
int mid = (l + r) >> 1;
int li = query_max(ql, qr, l, mid, ll(node));
int ri = query_max(ql, qr, mid + 1, r, rr(node));
if(li == -1){
return ri;
}
else if(ri == -1){
return li;
}
else{
double inv = query_inv(li + 1, ri);
double haritsa = ((double) y[ri]) / ((double) y[li]);
if(haritsa >= inv) return ri;
else return li;
}
}
int query_max(int ql, int qr){
return query_max(ql, qr, 0, n-1, 0);
}
// void update()
int init(int N, int X[], int Y[]){
n = N;
x.resize(n);
y.resize(n);
st_inv.resize(4*n);
st_max.resize(4*n);
for(int i = 0; i < n; i++){
x[i] = X[i];
y[i] = Y[i];
}
build_inv(0, n-1, 0);
build_max(0, n-1, 0);
// cout << query_max(0, n-1);
int indx = query_max(0, n-1);
int ret = 1;
for(int i = 0; i <= indx; i++){
ret *= x[i];
ret %= mod;
}
ret *= y[indx];
ret %= mod;
return ret;
}
int updateX(int pos, int val){
x[pos] = val;
update_inv(pos, 0, n-1, 0);
build_max(0, n-1, 0);
int indx = query_max(0, n-1);
int ret = 1;
for(int i = 0; i <= indx; i++){
ret *= x[i];
ret %= mod;
}
ret *= y[indx];
ret %= mod;
return ret;
}
int updateY(int pos, int val){
y[pos] = val;
build_max(0, n-1, 0);
int indx = query_max(0, n-1);
int ret = 1;
for(int i = 0; i <= indx; i++){
ret *= x[i];
ret %= mod;
}
ret *= y[indx];
ret %= mod;
return ret;
}
