// #ifdef __AVX2__
// #pragma GCC target "avx2"
// #endif
// #pragma GCC optimize "O3"
// #pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
#include "horses.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
// #define ordered_set tree<long long, null_type,less<long long>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<long long,long long>
#define fi first
#define se second
#define vec vector
// const long long mod=998244353;
const long long mod1=998244353;
const long long mod=1e9+7;
const long long N=5e5+5;
struct segtree{
long long size;
vector<long long>sums,ma;
void init(long long n){
size=1;
while(size<n) size*=2;
sums.assign(2*size,1);
ma=sums;
}
void set(long long i,long long v,long long x,long long lx,long long rx){
if(rx-lx==1){
sums[x]=v;
return;
}
long long m=(lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m);
}
else{
set(i,v,2*x+2,m,rx);
}
sums[x]=(sums[2*x+1]*sums[2*x+2])%mod;
}
void set(long long i, long long v){
set(i,v,0,0,size);
}
long long mul(long long l,long long r,long long x,long long lx,long long rx){
if(lx>=r or l>=rx) return 1;
if(lx>=l and rx<=r) return sums[x];
long long m=(lx+rx)/2;
long long s1=mul(l,r,2*x+1,lx,m);
long long s2=mul(l,r,2*x+2,m,rx);
return (s1*s2)%mod;
}
long long mul(long long l,long long r){
return mul(l,r+1,0,0,size);
}
long long mx(long long l,long long r,long long x,long long lx,long long rx){
if(lx>=r or l>=rx) return -1e18;
if(lx>=l and rx<=r) return ma[x];
long long m=(lx+rx)/2;
long long s1=mul(l,r,2*x+1,lx,m);
long long s2=mul(l,r,2*x+2,m,rx);
return max(s1,s2);
}
long long mx(long long l,long long r){
return mx(l,r+1,0,0,size);
}
void build(vector<long long>&a,long long x,long long lx,long long rx){
if(rx-lx==1){
if(lx<(long long)a.size()){
sums[x]=a[lx];
}
return;
}
long long m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
sums[x]=(sums[2*x+1]*sums[2*x+2])%mod;
}
void build(vector<long long>&a){
build(a,0,0,size);
}
};
vec<long long>x(N,0),y(N,0);
segtree segx,segy;
set<pii>seg;
long long n;
int ans(){
if(seg.empty())
return segy.mx(1,n);
vec<long long>ind,ri;
long long tem=1;
for(long long i=0;i<30;i++){
pii b=*seg.rbegin();
ind.append(b.fi);
ri.append(b.se);
seg.erase(b);
tem*=x[ind[i]];
if(tem>1e9 or seg.empty()) break;
}
reverse(all(ind));
reverse(all(ri));
long long ma=1;
tem=1;
for(long long i=0;i<ind.size();i++){
tem*=x[ind[i]];
ma=max(ma,tem*segy.mx(ind[i],ri[i]));
seg.insert(pai(ind[i],ri[i]));
}
ma%=mod;
ma=(ma*segx.mul(1,ind[0]-1))%mod;
return ma;
}
int updateX(int i,int v){
i++;
segx.set(i,v);
x[i]=v;
if(v==1){
if(x[i]==1) return ans();
auto p=seg.lower_bound(pai(i,0));
if(p!=seg.begin()){
auto p1=p;
p1--;
long long ind=((*p1).fi),r=((*p).se);
seg.erase(p1);
seg.insert(pai(ind,i-1));
seg.insert(pai(i,r));
}
else seg.insert(pai(i,(*seg.begin()).fi-1));
}
else{
if(x[i]>1) return ans();
auto p=seg.lower_bound(pai(i,0));
if(p!=seg.begin()){
auto p1=p;
p1--;
long long ind=((*p1).fi),si=((*p1).se);
seg.erase(p1);
seg.insert(pai(ind,(*p).se+si));
}
seg.erase(seg.lower_bound(pai(i,0)));
}
return ans();
}
int updateY(int i,int v){
i++;
segy.set(i,v);
y[i]=v;
return ans();
}
long long iter=1,itera=1;
int init(int N, int X[], int Y[]){
n=N;
segx.init(n+1);
for(long long i=1;i<=n;i++){
long long a=X[i-1];
x[i]=a;
segx.set(i,a);
}
segy.init(n+1);
for(long long i=1;i<=n;i++){
long long b=Y[i-1];
y[i]=b;
segy.set(i,b);
}
long long st=1,en=1;
for(long long i=2;i<=n;i++){
if(x[i]>1){
seg.insert(pai(st,en));
st=i;
en=i;
}
else{
en++;
}
}
seg.insert(pai(st,en));
if(x[1]==1) seg.erase(seg.begin());
return ans();
}
