#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 5, mod = 1000 * 1000 * 1000 + 7;
int n;
long long seg1[N * 4];
int seg2[N * 4];
set <int, greater<int> > s;
int a[N], b[N];
void update1(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg1[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update1(p, val, id * 2, s, md);
}
else {
update1(p, val, id * 2 + 1, md, e);
}
seg1[id] = (seg1[id * 2] * seg1[id * 2 + 1]) % mod;
}
void update2(int p, int val, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
seg2[id] = val;
return;
}
int md = (s + e) / 2;
if (p < md) {
update2(p, val, id * 2, s, md);
}
else {
update2(p, val, id * 2 + 1, md, e);
}
seg2[id] = max(seg2[id * 2], seg2[id * 2 + 1]);
}
long long get1(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 1;
}
if (l <= s && e <= r) {
return seg1[id];
}
int md = (s + e) / 2;
return (get1(l, r, id * 2, s, md) * get1(l, r, id * 2 + 1, md, e)) % mod;
}
int get2(int l, int r, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return 0;
}
if (l <= s && e <= r) {
return seg2[id];
}
int md = (s + e) / 2;
return max(get2(l, r, id * 2, s, md), get2(l, r, id * 2 + 1, md, e));
}
int getans() {
long long mp = 1;
long long ans = 0;
long long u = 1;
int mx = 0, mfor = 0;
long long mmp = 1;
set <int, greater <int> > :: iterator it = s.begin();
while (true) {
int k = *it;
if (k == -1) {
// ans = max(ans, get2(0, n));
break;
}
else {
// cout << "75 " << k << endl;
int t = get2(k, n);
long long s = get1(0, k + 1);
u = s;
s *= t;
s %= mod;
// cout << "78 " << k << " " << t << " " << s << " " << mp << endl;
if (mp * mx < t * mmp) {
mmp = mp;
mx = t;
mfor = k;
}
mp *= a[k];
}
if (mp > mod) {
break;
}
it++;
}
ans = get1(0, mfor + 1) * mx;
ans %= mod;
// cout << "74 " << mfor << " " << mx << " " << ans << endl;
return ans;
}
int init(int nn, int X[], int Y[]) {
n = nn;
fill(seg1, seg1 + n * 4, 1);
for (int i = 0; i < n; i++) {
a[i] = X[i];
b[i] = Y[i];
update1(i, a[i]);
update2(i, b[i]);
if (a[i] > 1) {
s.insert(i);
}
}
s.insert(-1);
s.insert(0);
// cout << "72 " << get1(0, 3) << " " << get2(0, 3) << endl;
return getans();
}
int updateX(int pos, int val) {
update1(pos, val);
if (val > 1) {
s.insert(pos);
}
else if(pos != 0) {
s.erase(pos);
}
a[pos] = val;
return getans();
}
int updateY(int pos, int val) {
update2(pos, val);
a[pos] = val;
return getans();
}
