#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;
const int LOG = 35;
struct Node {
ll prodX, mxX, mxY; int posMxY;
Node(ll _prodX=1, ll _mxX=-INF, ll _mxY=-INF):
prodX(_prodX), mxX(_mxX), mxY(_mxY) {}
Node operator+(Node right) {
Node left = *this;
return Node(
(left.prodX * right.prodX) % MOD,
max(left.mxX, right.mxX),
max(left.mxY, right.mxY)
);
}
};
struct SEG {
vector<Node> seg; int n; vector<tuple<int, int, int>> rngs;
SEG(int _n=0) {
n = 1;
while (n < _n) n <<= 1;
seg = vector<Node> (2*n);
}
int getLeft(int v) {
return 2*v;
}
int getRight(int v) {
return 2*v+1;
}
void upd(int v, int l, int r, int i, Node val) {
if (l == r) {
seg[v] = val;
return;
}
int m = (l + r) / 2;
if (i <= m) upd(getLeft(v), l, m, i, val);
else upd(getRight(v), m+1, r, i, val);
seg[v] = seg[getLeft(v)] + seg[getRight(v)];
}
Node rng(int v, int l, int r, int a, int b) {
if (a <= l and r <= b) {
return seg[v];
}
if (r < a or b < l) return Node();
int m = (l + r) / 2;
return rng(getLeft(v), l, m, a, b) + rng(getRight(v), m+1, r, a, b);
}
void saveRngs(int v, int l, int r, int a, int b) {
if (a <= l and r <= b) {
rngs.emplace_back(v, l, r);
return;
}
if (r < a or b < l) return;
int m = (l + r) / 2;
saveRngs(getRight(v), m+1, r, a, b);
saveRngs(getLeft(v), l, m, a, b);
}
int nxt(int v, int l, int r) {
if (l == r) return l;
int m = (l + r) / 2;
if (seg[getRight(v)].mxX >= 2) return nxt(getRight(v), m+1, r);
else return nxt(getLeft(v), l, m);
}
int nxt(int x) {
// primeiro X[i] >= 2
int res = 0;
saveRngs(1, 0, n-1, 0, x);
for (auto [v, l, r] : rngs) {
if (seg[v].mxX == 1) continue;
res = nxt(v, l, r);
break;
}
rngs.clear();
return res;
}
};
int n;
SEG seg;
int getAns() {
ll mxY = 0, mxProdX = 0; int ans = 0;
for (int i=1, pos = n-1; i<=min(LOG, n) and mxProdX * mxY <= 1000000000LL and pos >= 0; i++) {
int newPos = seg.nxt(pos);
Node node = seg.rng(1, 0, seg.n-1, newPos, newPos);
Node rng = seg.rng(1, 0, seg.n-1, newPos, pos);
ll x = node.mxX, y = rng.mxY;
if (mxProdX * mxY < y) {
mxY = y;
mxProdX = 1;
ans = newPos;
}
mxProdX *= x;
// cout << newPos << ' ' << x << ' ' << y << endl;
pos = newPos - 1;
}
// cout << endl;
return (int)((seg.rng(1, 0, seg.n-1, 0, ans).prodX * mxY) % MOD);
}
int init(int N, int X[], int Y[]) {
n = N;
seg = SEG(n);
for (int i=0; i<n; i++)
seg.upd(1, 0, seg.n-1, i, Node(X[i], X[i], Y[i]));
return getAns();
}
int updateX(int pos, int val) {
Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
curr.mxX = val; curr.prodX = val;
seg.upd(1, 0, seg.n-1, pos, curr);
return getAns();
}
int updateY(int pos, int val) {
Node curr = seg.rng(1, 0, seg.n-1, pos, pos);
curr.mxY = val;
seg.upd(1, 0, seg.n-1, pos, curr);
return getAns();
}
