#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
int modulo = (int)1e9 + 7;
int x[500005], y[500005];
int n;
set<int> grx;
int aint[2000005];
void build(int nod, int l, int r)
{
if (l == r)
aint[nod] = y[l];
else
{
int mij = (l + r) / 2;
build(2 * nod,l,mij);
build(2 * nod + 1,mij + 1,r);
aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}
}
void update(int nod, int l, int r, int pos, int val)
{
if (l == r)
aint[nod] = val;
else
{
int mij = (l + r) / 2;
if (pos <= mij)
update(2 * nod,l,mij,pos,val);
else
update(2 * nod + 1,mij + 1,r,pos,val);
aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}
}
int query(int nod, int l, int r, int st, int dr)
{
if (r < st or dr < l)
return 0;
if (st <= l and r <= dr)
return aint[nod];
int mij = (l + r) / 2;
return max(query(2 * nod,l,mij,st,dr), query(2 * nod + 1,mij + 1,r,st,dr));
}
int solve()
{
vector<pair<ll, pair<int,int>>> candi;
vector<int> depus;
ll prd = 1;
int r = n;
while (!grx.empty() and prd < (int)1e9)
{
int l = *grx.rbegin();
candi.push_back({x[l], {l,r}});
depus.push_back(l);
grx.erase(l);
prd *= x[l];
r = l - 1;
}
if (prd < (int)1e9 and r >= 1)
candi.push_back({1,{1,r}});
reverse(candi.begin(),candi.end());
for (int i = 0; i + 1 < candi.size(); i++)
candi[i + 1].first *= candi[i].first;
__int128 ans = 0;
for (auto it : candi)
{
__int128 prr = it.first;
__int128 prr2 = query(1,1,n,it.second.first,it.second.second);
prr *= prr2;
ans = max(ans,prr);
}
for (auto it : depus)
grx.insert(it);
ans %= modulo;
return ans;
}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 1; i <= n; i++)
x[i] = X[i - 1], y[i] = Y[i - 1];
for (int i = 1; i <= n; i++)
if (x[i] > 1)
grx.insert(i);
build(1,1,n);
return solve();
}
int updateX(int pos, int val)
{
pos++;
if (x[pos] > 1)
grx.erase(pos);
x[pos] = val;
if (x[pos] > 1)
grx.insert(val);
return solve();
}
int updateY(int pos, int val)
{
pos++;
update(1,1,n,pos,val);
return solve();
}
