#include <iostream>
#include <set>
#include "horses.h"
using namespace std;
#define ll long long
const long long mod = 1000000007;
const long long mx = 1000000018;
int n;
int x[501010], y[501010];
int t[2010101];
int Mxt[2010101];
multiset<int> Lf;
int Rf[501010];
void build(int v, int vl, int vr) {
if (vl == vr) {
t[v] = x[vl];
Mxt[v] = vl;
return;
}
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;
if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
Mxt[v] = Mxt[2 * v];
else
Mxt[v] = Mxt[2 * v + 1];
}
void upd(int v, int vl, int vr, int pos, int val) {
if (vl == vr) {
t[v] = val % mod;
return;
}
int vm = (vl + vr) / 2;
if (pos <= vm)upd(2 * v, vl, vm, pos, val);
else upd(2 * v + 1, vm + 1, vr, pos, val);
t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;
}
void Mxupd(int v, int vl, int vr, int pos) {
if (vl == vr) {
Mxt[v] = vl;
return;
}
int vm = (vl + vr) / 2;
if (pos <= vm)Mxupd(2 * v, vl, vm, pos);
else Mxupd(2 * v + 1, vm + 1, vr, pos);
if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
Mxt[v] = Mxt[2 * v];
else
Mxt[v] = Mxt[2 * v + 1];
}
int gt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return t[v] % mod;
if (r < vl || vr < l)return 1ll;
int vm = (vl + vr) / 2;
return ((ll)gt(2 * v, vl, vm, l, r) * (ll)gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
}
int Mxgt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return Mxt[v];
if (r < vl || vr < l)return -1;
int vm = (vl + vr) / 2;
int f = Mxgt(2 * v, vl, vm, l, r);
int s = Mxgt(2 * v + 1, vm + 1, vr, l, r);
if (f == -1)return s;
if (s == -1)return f;
if (y[f] < y[s])return s;
return f;
}
set<int>::iterator Aps;
int gtspec(int i) {
if (*Aps == 1010101010)--Aps;
while (i < *Aps)--Aps;
int NUM = *Aps;
if (NUM == -1)return i - 1;
if (NUM <= i && i <= Rf[NUM])return (NUM - 1);
return i - 1;
}
int opp() {
Aps = --Lf.end();
int cnt = y[n - 1];
int last = n - 1;
for (int i = n - 1; i > 0;) {
if (x[i] > mx / cnt)cnt = mx;
else cnt *= x[i];
if (cnt == mx)break;
if (x[i] > 1) {
if (cnt < y[i - 1]){last = i - 1;cnt = y[i - 1];i--;continue;}
}
int r = gtspec(i);
int p = Mxgt(1, 0, n - 1, r, i);
i = r;
if (cnt < y[p]){last = p;cnt = y[p];}
}
int d = gt(1, 0, n - 1, 0, last);
return ((d % mod) * (y[last] % mod)) % mod;
}
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];
}
build(1, 0, n - 1);
int l = -1;
for (int i = 0; i < n; i++) {
if (x[i] == 1) {
if (l == -1)l = i;
if (i == n - 1 || x[i + 1] != 1) {
Lf.insert(l);
Rf[l] = i;
}
} else {
l = -1;
}
}
Lf.insert(-1); Lf.insert(1010101010);
return opp();
}
int updateX(int pos, int val) {
if (x[pos] == 1 && val != 1) {
auto it = Lf.upper_bound(pos); --it;
int sv = Rf[*it];
if (*it <= pos - 1) {
Rf[*it] = pos - 1;
} else Lf.erase(it);
if (pos + 1 <= sv) {
Lf.insert(pos + 1);
Rf[pos + 1] = sv;
}
} else if (x[pos] != 1 && val == 1) {
auto s = Lf.upper_bound(pos);
auto f = s; --f;
int S = *s, F = *f;
if (F != -1 && Rf[F] == pos - 1 && pos + 1 == S) {
Lf.erase(s);
Lf.insert(F);
Rf[F] = Rf[S];
} else if (F != -1 && Rf[F] == pos - 1) {
Rf[F]++;
} else if (pos + 1 == S) {
Lf.erase(s);
Lf.insert(S - 1);
Rf[S - 1] = Rf[S];
}
}
x[pos] = val;
upd(1, 0, n - 1, pos, val);
return opp();
}
int updateY(int pos, int val) {
y[pos] = val;
Mxupd(1, 0, n - 1, pos);
return opp();
}
/**
0 1 2 3 4 5 6 7 8 9
10 10 10 10 10 1 1 1 1 1
*/
