// #include<bits/aintocator.h>
// #pragma GCC optimize("Ofast,unroint-loops")
// #ifdef ONLINE_JUDGE
// #pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")
// #endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#include "horses.h"
// VVI
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0);
#define SZ(a) (int)a.size()
#define UNIQUE(a) (a).erase(unique(aint(a)), (a).end())
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a))
#define aint(x) x.begin(), x.end()
//Printings & debugging
#define nn '\n'
#define Setpre(n) cout << fixed << setprecision(n)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define debug printf("I am here\n")
// CONSTANTS
#define md 1000007
#define PI acos(-1)
const long double EPS = 1e-9;
const int N = 2e5 + 10;
const int M = 1e9 + 7;
/// INLINE FUNCTIONS
inline int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
inline int LCM(int a, int b) { return a * b / GCD(a, b); }
inline long double logb(int base, int num) { return ( long double )log(num) / ( long double )log(base); }
const int INF=1e15+500;
// int mul(int x) {return x==0 ? 1 : mul(x-1)*10;}
const int MAXN=3e5+100;
const int MOD=1e9+7;
#define p(i,n) for(int i=0; i<n; i++)
#define rp(i,n) for(int i=n-1; i>=0; i--)
#define grid_int vector<vector<int>>
#define grid_char vector<vector<char>>
void ADD(int& c,int a, int b, int m) {c = ((a % m) + (b % m)) % m;return;}
void MUL(int& c,int a, int b, int m) {c = ((a % m) * (b % m)) % m;}
void SUB(int& c,int a, int b, int m) {c = ((a % m) - (b % m) + m) % m;}
void MIN(int& a, int b) {a = min(a, b);}
void MAX(int& a, int b) {a = max(a, b);}
int gcdExtended(int a, int b, int *x, int *y);
int modInverse(int b, int m){int x,y;int g = gcdExtended(b, m, &x, &y);if (g != 1)return -1;return (x%m + m) % m;}
int modDivide(int a, int b, int m){a = a % m;int inv = modInverse(b, m);return (inv * a) % m;}
int gcdExtended(int a, int b, int *x, int *y){if (a == 0){*x = 0, *y = 1;return b;}int x1, y1;int gcd = gcdExtended(b%a, a, &x1, &y1);*x = y1 - (b/a) * x1;*y = x1;return gcd;}
#define f first
#define s second
#define ll long long
#define pb push_back//SEGGY FOR max pref sum;
vector<int> xi, yi;
int nnn;
struct item {
double lg;
int idx;
int val;
// VAL IS THE XI
// LG IS LOG OF SELLING AT DAY index
// iDX IS INDEX
};
struct segtree {
vector<item> seggy;
vector<double> lazy;
int n;
segtree(int _n) {
n = _n;
seggy.resize(4 * n);
lazy.resize(4 * n, 0);
}
item merge(item a, item b) {
item x;
if (a.lg > b.lg) {
x.lg = a.lg;
x.idx = a.idx;
} else {
x.lg = b.lg;
x.idx = b.idx;
}
MUL(x.val, a.val, b.val, MOD);
return x;
}
void push(int node, int left, int right) {
if (lazy[node] != 0) {
seggy[node].lg += lazy[node];
if (left != right) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
}
void build(int node, int left, int right) {
if (left == right) {
seggy[node].idx = left;
seggy[node].lg = log(yi[left]);
seggy[node].val = xi[left];
} else {
int mid = (left + right) / 2;
build(2 * node, left, mid);
build(2 * node + 1, mid + 1, right);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
}
// Point update to set new value and log
void update(int node, int left, int right, int idx, int vv) {
push(node, left, right);
if (left == right) {
seggy[node].idx = left;
seggy[node].lg = log(vv);
seggy[node].val = vv;
} else {
int mid = (left + right) / 2;
if (idx > mid) update(2 * node + 1, mid + 1, right, idx, vv);
else update(2 * node, left, mid, idx, vv);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
}
// Point update to add value to lg
void update_lg(int node, int left, int right, int idx, double vv) {
push(node, left, right);
if (left == right) {
seggy[node].idx = left;
seggy[node].lg += vv;
return;
}
int mid = (left + right) / 2;
if (idx > mid) update_lg(2 * node + 1, mid + 1, right, idx, vv);
else update_lg(2 * node, left, mid, idx, vv);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
// New range update function for .lg using lazy propagation
void lazyx(int node, int left, int right, int l, int r, double add_val) {
push(node, left, right);
if (r < left || l > right) return;
if (l <= left && right <= r) {
lazy[node] += add_val;
push(node, left, right);
return;
}
int mid = (left + right) / 2;
lazyx(2 * node, left, mid, l, r, add_val);
lazyx(2 * node + 1, mid + 1, right, l, r, add_val);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
int query(int node, int left, int right, int l, int r) {
push(node, left, right);
if (l > right || r < left) return 1;
if (left >= l && right <= r) return seggy[node].val % MOD;
int mid = (left + right) / 2;
int xx = query(2 * node, left, mid, l, r);
int yy = query(2 * node + 1, mid + 1, right, l, r);
int temp;
MUL(temp, xx, yy, MOD);
return temp;
}
item grab() {
return seggy[1]; // root is usually at index 1
}
};
segtree Tree(5e5+10);
int opt(vector<int>& a, vector<int>& b, int n) {
item x = Tree.grab();
int ppp = Tree.query(1, 0, nnn - 1, 0, x.idx);
int temp;
MUL(temp, ppp, yi[x.idx], MOD);
return temp;
}
// the functions that are asked by the grader
int init(int n, int X[], int Y[]) {
nnn = n;
xi.resize(nnn);
yi.resize(nnn);
for (int i = 0; i < n; i++) {
xi[i] = X[i];
Tree.lazyx(1,0,n-1,i,n-1,log(xi[i]));
}
for (int i = 0; i < n; i++) yi[i] = Y[i];
Tree.build(1,0,n-1);
return opt(xi, yi, n);
}
int updateX(int pos, int val) {
Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(xi[pos]));
xi[pos] = val;
Tree.update(1, 0, nnn - 1, pos, val);
return opt(xi, yi, nnn);
}
int updateY(int pos, int val) {
Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(yi[pos]));
yi[pos] = val;
return opt(xi, yi, nnn);
}
