#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
vector<pair<int, int>> maxy;
void umy(int curin, int curl, int curr, int in, int val) {
if (in < curl || in > curr)
return;
if (curl == curr) {
maxy[curin] = {val, curl};
return;
}
umy(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
umy(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
maxy[curin] = max(maxy[curin * 2 + 1], maxy[curin * 2 + 2]);
}
pair<int, int> qmy(int curin, int curl, int curr, int ql, int qr) {
if (curl > qr || curr < ql)
return {-1, -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));
}
vector<ll> totcap;
void utp(int curin, int curl, int curr, int in, int val) {
if (in < curl || in > curr)
return;
if (curl == curr) {
totcap[curin] = val;
return;
}
utp(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
utp(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
if (totcap[curin * 2 + 1] >= MOD || totcap[curin * 2 + 2] >= MOD ||
totcap[curin * 2 + 1] * totcap[curin * 2 + 2] >= MOD)
totcap[curin] = MOD;
else
totcap[curin] = totcap[curin * 2 + 1] * totcap[curin * 2 + 2];
}
ll qtp(int curin, int curl, int curr, int ql, int qr) {
if (ql > curr || qr < curl)
return 1;
if (curl == curr) {
return totcap[curin];
}
ll a = qtp(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
b = qtp(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr);
if (a >= MOD || b >= MOD || a * b >= MOD)
return MOD;
return a * b;
}
vector<ll> totval;
void utl(int curin, int curl, int curr, int in, int val) {
if (in < curl || in > curr)
return;
if (curl == curr) {
totval[curin] = val;
return;
}
utl(curin * 2 + 1, curl, (curl + curr) / 2, in, val);
utl(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
totval[curin] = totval[curin * 2 + 1] * totval[curin * 2 + 2] % MOD;
}
ll qtl(int curin, int curl, int curr, int ql, int 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;
}
int n;
vector<ll> x, y;
set<int, greater<int>> sigi;
int ans() {
vector<int> vi;
auto it = sigi.begin();
for (int i = 0; i < min(30, (int)sigi.size()); i++) {
vi.push_back(*it);
it++;
}
reverse(vi.begin(), vi.end());
vi.push_back(n);
// cout << "X: ";
// for (int i = 0; i < n; i++) {
// cout << x[i] << ' ';
// }
// cout << "\n";
//
// cout << "Y: ";
// for (int i = 0; i < n; i++) {
// cout << y[i] << ' ';
// }
// cout << "\n";
//
// cout << "VI: ";
// for (auto a : vi)
// cout << a << ' ';
// cout << "\n";
int maxin = qmy(0, 0, n - 1, vi[0], vi[1] - 1).second;
// cout << "FIRSTMAXIN = " << maxin << "\n";
for (int i = 1; i + 1 < vi.size(); i++) {
int curin = qmy(0, 0, n - 1, vi[i], vi[i + 1] - 1).second;
ll diff = qtp(0, 0, n - 1, maxin + 1, curin);
// cout << "Diff = " << diff << "\n";
if (diff * y[curin] > y[maxin]) {
maxin = curin;
}
}
// cout << "MAXIN = " << maxin << "\n";
return qtl(0, 0, n - 1, 0, maxin) * y[maxin] % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
maxy = vector<pair<int, int>>(4 * n);
totval = totcap = vector<ll>(4 * n);
y = x = vector<ll>(n);
for (int i = 0; i < n; i++) {
umy(0, 0, n - 1, i, Y[i]);
utp(0, 0, n - 1, i, X[i]);
utl(0, 0, n - 1, i, X[i]);
x[i] = X[i], y[i] = Y[i];
}
for (int i = 0; i < n; 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), utp(0, 0, n - 1, pos, val);
if (x[pos] >= 2)
sigi.erase(pos);
x[pos] = val;
if (x[pos] >= 2)
sigi.insert(pos);
sigi.insert(0);
return ans();
}
int updateY(int pos, int val) {
umy(0, 0, n - 1, pos, val);
y[pos] = val;
return ans();
}
