#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using Node = pair<double, int>;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n;
vector<int> X(5*maxn), Y(5*maxn), PS(5*maxn);
vector<double> logX(5*maxn), logY(5*maxn), PL(5*maxn);
Node merge(Node a, Node b) {
if(a.first > b.first) return a;
return b;
}
struct SegTree {
int N;
vector<ll> prod;
vector<Node> tree;
vector<double> lazy;
void init() {
N = n;
prod.resize(5*N+5);
tree.resize(5*N+5);
lazy.resize(5*N+5);
build(1, 0, N-1);
}
void push(int u, int tl, int tr) {
if(lazy[u] == 0) return ;
tree[u].first += lazy[u];
if(tl != tr) {
lazy[2*u] += lazy[u];
lazy[2*u+1] += lazy[u];
}
lazy[u] = 0;
}
void build(int u, int tl, int tr) {
if(tl == tr) {
tree[u] = { PL[tl] + logY[tl], tl };
prod[u] = X[tl];
} else {
int tm = (tl + tr) / 2;
build(2*u, tl, tm);
build(2*u+1, tm+1, tr);
prod[u] = (prod[2*u] * prod[2*u+1]) % mod;
tree[u] = merge(tree[2*u], tree[2*u+1]);
}
}
void updateProd(int u, int tl, int tr, int pos, int val) {
if(tl == tr) {
prod[u] = val;
} else {
int tm = (tl + tr) / 2;
if(pos <= tm)
updateProd(2*u, tl, tm, pos, val);
else
updateProd(2*u+1, tm+1, tr, pos, val);
prod[u] = (prod[2*u] * prod[2*u+1]) % mod;
}
}
void updatePos(int u, int tl, int tr, int l, int r, double val) {
push(u, tl, tr);
if(tl > tr || tl > r || l > tr) return ;
if(l <= tl && tr <= r) {
lazy[u] += val;
push(u, tl, tr);
return ;
}
int tm = (tl + tr) / 2;
updatePos(2*u, tl, tm, l, r, val);
updatePos(2*u+1, tm+1, tr, l, r, val);
tree[u] = merge(tree[2*u], tree[2*u+1]);
}
ll getProd(int u, int tl, int tr, int l, int r) {
if(tl > tr || l > tr || tl > r) return 1;
if(l <= tl && tr <= r) return prod[u];
int tm = (tl + tr) / 2;
return (
getProd(2*u, tl, tm, l, r) *
getProd(2*u+1, tm+1, tr, l, r)
) % mod;
}
Node getPos(int u, int tl, int tr, int l, int r) {
if(tl > tr || l > tr || tl > r) return { -1e18, 0 };
push(u, tl, tr);
if(l <= tl && tr <= r) return tree[u];
int tm = (tl + tr) / 2;
return merge(
getPos(2*u, tl, tm, l, r),
getPos(2*u+1, tm+1, tr, l, r)
);
}
void updateProd(int pos, int val) { updateProd(1, 0, N-1, pos, val); }
ll getProd(int p) { return getProd(1, 0, N-1, 0, p); }
int getPos() { return getPos(1, 0, N-1, 0, N-1).second; }
void updatePos(int l, int r, double val) { updatePos(1, 0, N-1, l, r, val); }
} tree;
int calc() {
int pos = tree.getPos();
ll ans = (tree.getProd(pos) * Y[pos]) % mod;
return (int)ans;
}
int init(int N, int x[], int y[]) {
n = N;
for(int i=0; i<n; i++) {
X[i] = x[i], Y[i] = y[i];
PS[i] = X[i];
if(i) PS[i] = (1ll * PS[i] * PS[i-1]) % mod;
logX[i] = log2(X[i]), logY[i] = log2(y[i]);
PL[i] = logX[i];
if(i) PL[i] += PL[i-1];
}
tree.init();
return calc();
}
int updateX(int p, int v) {
tree.updatePos(p, n-1, -logX[p]);
X[p] = v, logX[p] = log2(v);
tree.updateProd(p, v);
tree.updatePos(p, n-1, log2(v));
return calc();
}
int updateY(int p, int v) {
tree.updatePos(p, p, -logY[p]);
Y[p] = v, logY[p] = log2(v);
tree.updatePos(p, p, log2(v));
return calc();
}
