#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long MOD = 1e9 + 7;
const long long mn = 5e5;
long long maxy[4 * mn];
void umy(long long curin, long long curl, long long curr, long long in,
long long val) {
if (curl == curr) {
maxy[curin] = val;
return;
}
long long mid = (curl + curr) / 2;
if (in <= mid)
umy(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
else
umy(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
maxy[curin] = max(maxy[curin * 2 + 1], maxy[curin * 2 + 2]);
}
long long qmy(long long curin, long long curl, long long curr, long long ql,
long long qr) {
if (curl > qr || curr < ql)
return -1;
if (curl == curr) {
return maxy[curin];
}
return max(qmy(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
qmy(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}
ll totval[4 * mn];
void utl(long long curin, long long curl, long long curr, long long in,
long long val) {
if (curl == curr) {
totval[curin] = val;
return;
}
long long mid = (curl + curr) / 2;
if (in <= mid)
utl(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
else
utl(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
totval[curin] = totval[curin * 2 + 1] * totval[curin * 2 + 2] % MOD;
}
ll qtl(long long curin, long long curl, long long curr, long long ql,
long long qr) {
if (ql > curr || qr < curl)
return 1;
if (curl == curr) {
return totval[curin];
}
ll a = qtl(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
b = qtl(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr);
return a * b % MOD;
}
long long n;
vector<ll> x, y;
set<long long, greater<long long>> sigi;
long long ans() {
// cout << "X: ";
// for ( long long i = 0; i < n; i++) {
// cout << x[i] << ' ';
// }
// cout << "\n";
//
// cout << "Y: ";
// for ( long long i = 0; i < n; i++) {
// cout << y[i] << ' ';
// }
// cout << "\n";
long long maxyval = qmy(0, 0, n - 1, *sigi.begin(), n - 1);
long long maxin = *sigi.begin();
// cout << "FIRSTMAXIN = " << maxin << "\n";
auto it = sigi.begin();
long long prev = *it;
ll diff = x[*it];
for (++it; it != sigi.end(); it++) {
long long yval = qmy(0, 0, n - 1, *it, prev - 1);
// cout << *it << " " << prev << '\n';
// cout << "Curin " << curin << " " << maxin << "\n";
// cout << "Diff = " << diff << "\n";
if (diff * maxyval >= MOD)
return qtl(0, 0, n - 1, 0, maxin) * maxyval % MOD;
if (diff * maxyval < yval) {
maxyval = yval;
maxin = *it;
diff = 1;
}
diff *= x[*it];
prev = *it;
}
// cout << "MAXIN = " << maxin << "\n";
return qtl(0, 0, n - 1, 0, maxin) * maxyval % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
y = x = vector<ll>(n);
for (long long i = 0; i < n; i++) {
umy(0, 0, n - 1, i, Y[i]);
utl(0, 0, n - 1, i, X[i]);
x[i] = X[i], y[i] = Y[i];
if (X[i] >= 2)
sigi.insert(i);
}
sigi.insert(0);
return ans();
}
int updateX(int pos, int val) {
utl(0, 0, n - 1, pos, val);
long long orig = x[pos];
x[pos] = val;
if ((pos == 0) || ((orig >= 2) == (val >= 2)))
return ans();
if (orig >= 2)
sigi.erase(pos);
else
sigi.insert(pos);
return ans();
}
int updateY(int pos, int val) {
umy(0, 0, n - 1, pos, val);
y[pos] = val;
return ans();
}
