#include <bits/stdc++.h>
#include "horses.h"
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e5 + 5;
int n;
int x[N], y[N];
bool inside[N];
struct segtree {
struct node {
int val;
bool exceed;
node() : val(0), exceed(0) {}
};
node seg[4 * N];
node create(){
node newnode;
newnode.val = 1;
newnode.exceed = 0;
return newnode;
}
node merge(node l, node r){
node newnode = create();
newnode.exceed = (l.exceed || r.exceed);
newnode.val = (l.val * r.val) % mod;
if ((l.val * r.val) >= mod) newnode.exceed = true;
return newnode;
}
void build(int l, int r, int i){
if (l == r) return seg[i].val = x[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
}
void update(int l, int r, int i, int idx, int val){
if (l == r) return seg[i].val = val, void();
int mid = (l + r) / 2;
if (idx <= mid) update(l, mid, 2 * i, idx, val);
else update(mid + 1, r, 2 * i + 1, idx, val);
seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
}
node query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return create();
int mid = (l + r) / 2;
return merge(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} seg;
struct indexmaintain {
int seg[4 * N];
void build(int l, int r, int i){
if (l == r) return seg[i] = (x[l] > 1), void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
void update(int l, int r, int i, int idx, int val){
if (l == r) return seg[i] = (val > 1), void();
int mid = (l + r) / 2;
if (idx <= mid) update(l, mid, 2 * i, idx, val);
else update(mid + 1, r, 2 * i + 1, idx, val);
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
int query(int l, int r, int i, int k){
if (l == r) return l;
int mid = (l + r) / 2;
if (seg[2 * i + 1] >= k) return query(mid + 1, r, 2 * i + 1, k);
else return query(l, mid, 2 * i, k - seg[2 * i + 1]);
}
} indices;
struct mxseg{
int seg[4 * N];
void build(int l, int r, int i){
if (l == r) return seg[i] = y[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
void update(int l, int r, int i, int idx, int val){
if (l == r) return seg[i] = val, void();
int mid = (l + r) / 2;
if (idx <= mid) update(l, mid, 2 * i, idx, val);
else update(mid + 1, r, 2 * i + 1, idx, val);
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
int query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return 0;
int mid = (l + r) / 2;
return max(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} mxx;
int query(){
int st = 1, exact = indices.seg[1];
for (int i = 1; i <= indices.seg[1]; i++) {
int idx = indices.query(1, n, 1, i);
// cout << i << ": " << idx << ": " << seg.query(1, n, 1, idx, n).exceed << "\n";
if (seg.query(1, n, 1, idx, n).exceed) {
st = idx;
exact = i;
break;
}
}
if (indices.seg[1] == 0) return mxx.query(1, n, 1, 1, n);
long double mx = 0;
long double prod = 1.0;
int num = 1, prodmod = 1;
int fst = indices.query(1, n, 1, exact);
if (st < fst) {
int val = mxx.query(1, n, 1, st, fst - 1);
mx = val;
num = val % mod;
}
for (int i = exact; i >= 1; i--) {
int idx = indices.query(1, n, 1, i);
prod *= x[idx];
prodmod = (prodmod * x[idx]) % mod;
int nxt = (i == 1 ? n + 1 : indices.query(1, n, 1, i - 1));
int mxy = mxx.query(1, n, 1, idx, nxt - 1);
if (prod * mxy > mx) {
mx = prod * mxy;
num = (prodmod * mxy) % mod;
}
}
int answer = ((seg.query(1, n, 1, 1, st - 1).val * num) % mod);
return answer;
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
n = N;
for (int i = 0; i < n; i++) x[i + 1] = X[i];
for (int i = 0; i < n; i++) y[i + 1] = Y[i];
y[0] = 1;
seg.build(1, n, 1);
indices.build(1, n, 1);
mxx.build(1, n, 1);
return query();
}
int32_t updateX(int32_t pos, int32_t val) {
++pos;
x[pos] = val;
seg.update(1, n, 1, pos, val);
indices.update(1, n, 1, pos, val);
return query();
}
int32_t updateY(int32_t pos, int32_t val) {
++pos;
y[pos] = val;
mxx.update(1, n, 1, pos, val);
return query();
}
// int32_t main(){
// int32_t n; cin >> n;
// int32_t x[n], y[n];
// for (int i = 0; i < n; i++) cin >> x[i];
// for (int i = 0; i < n; i++) cin >> y[i];
// cout << init(n, x, y) << "\n";
// int32_t m; cin >> m;
// while (m--) {
// int t; cin >> t;
// int pos, val; cin >> pos >> val;
// if (t == 1) cout << updateX(pos, val) << "\n";
// else cout << updateY(pos, val) << "\n";
// }
// }
