#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define FORi(i,a,b) for(int i=a;i<b;i++)
#define MOD 1000000007
#define FOR(i,n) FORi(i,0,n)
#define ll long long
#define MID ((l+r)/2)
#define len(x) ((int)((x).size()))
#define F first
#define S second
template<typename T>
struct seg_tree{
struct node{
T val;
node* left=NULL;
node* right=NULL;
node() {val=0, left=NULL, right=NULL;}
node(T v) {val=v, right=NULL, left=NULL;}
};
static inline node *root=NULL;
static inline int N;
const int RAND_VALUE=1;
seg_tree(int n){N=n, root = new node();}
seg_tree(){root = new node();}
inline void merge(node *par){
par->val = max(par->left->val , par->right->val);
}
inline void update_node(node* ind, int val){
ind->val = val;
}
void build(vector<T>& arr, int l=0, int r=N-1, node *ind=root){
if(l==r) ind->val = arr[l];
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
build(arr,l,MID,ind->left);
build(arr,MID+1,r,ind->right);
merge(ind);
}
}
void update(int rl, int rr, int val, int l=0, int r=N-1, node* ind=root){
if(rl<=l && r<=rr) update_node(ind, val);
else if(rr<l || r<rl) return;
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
update(rl,rr,val,l,MID,ind->left);
update(rl,rr,val,MID+1,r,ind->right);
merge(ind);
}
}
T query(int rl, int rr, int l=0, int r=N-1, node* ind=root){
if(rl<=l && r<=rr) return ind->val;
else if(rl>r || l>rr) return RAND_VALUE;
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
T ret=0;
ret = max(ret, query(rl,rr,l,MID,ind->left));
ret = max(ret, query(rl,rr,MID+1,r,ind->right));
return ret;
}
}
};
struct mult_seg_tree{
struct node{
double vald;
int valm;
node* left=NULL;
node* right=NULL;
node() {vald=0, valm=0, left=NULL, right=NULL;}
node(double v, int m) {vald=v, valm=m,right=NULL, left=NULL;}
};
static inline node *root=NULL;
static inline int N;
const int RAND_VALUE=1;
mult_seg_tree(int n){N=n, root = new node();}
mult_seg_tree(){root = new node();}
inline void merge(node *par){
par->vald = par->left->vald * par->right->vald;
par->valm = (((ll)par->left->valm) * ((ll)par->right->valm)) % MOD;
}
inline void update_node(node* ind, int val){
ind->valm = val;
ind->vald = val;
}
void build(vector<int>& arr, int l=0, int r=N-1, node *ind=root){
if(l==r) ind->vald = arr[l], ind->valm = arr[l];//, cout<<l<<" "<<arr[l]<<endl;
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
build(arr,l,MID,ind->left);
build(arr,MID+1,r,ind->right);
merge(ind);
}
}
void update(int rl, int rr, int val, int l=0, int r=N-1, node* ind=root){
if(rl<=l && r<=rr) update_node(ind, val);
else if(rr<l || r<rl) return;
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
update(rl,rr,val,l,MID,ind->left);
update(rl,rr,val,MID+1,r,ind->right);
merge(ind);
}
}
pair<int,double> query(int rl, int rr, int l=0, int r=N-1, node* ind=root){
if(rl<=l && r<=rr) return make_pair(ind->valm, ind->vald);
else if(rl>r || l>rr) return make_pair(RAND_VALUE, RAND_VALUE);
else{
if(ind->left==NULL) ind->left = new node();
if(ind->right==NULL) ind->right = new node();
pair<int,double> res1 = query(rl,rr,l,MID,ind->left);
pair<int,double> res2 = query(rl,rr,MID+1,r,ind->right);
double ret1 = res1.S * res2.S;
ll ret2=res1.F * res2.F;
ret2%=MOD;
return make_pair(ret2, ret1);
}
}
};
typedef vector<int> vi;
vi x;
vector<int> y;
vector<double> a;
set<int> xx;
clock_t start_timer;
void time_start(){
start_timer = clock();
}
void time_end(){
auto endt = clock();
//cout<<(double)(endt-start_timer) / CLOCKS_PER_SEC<<endl;
}
seg_tree<int> yseg;
mult_seg_tree xseg;
#define FOA(v,qq) for(auto v : qq)
int get_ans(){
auto it = xx.end();
it--;
it--;
int cnt=0;
double maxa=0;
int ansa=1;
// O(30)
auto itt = xx.end();
ll pp=1;
auto st = it;
auto vv = yseg.query(0,yseg.N-1);
while(itt!=xx.begin() && pp<vv) itt--, pp*=x[*itt], st=itt;
int f = *itt;
//cout<<f<<endl;
// O(30logN)
while(1){
auto it2 = it;
it2++;
// O(logN)
//cout<<*it<<" "<<*it2<<endl;
pair<int,double> res = xseg.query(f, *it);
double c = res.S;
assert(c>0);
// O(logN)
int res2 = yseg.query(*it, *it2-1);
//cout<<c<<" ";
c*=res2;
//cout<<c<<endl;
if(c>maxa){
maxa = c;
ansa = (((ll)res.F) * ((ll)res2)) % MOD;
}
cnt++;
if(it==st) break;
it--;
}
ansa = (((ll)xseg.query(0, f-1).F) * ansa) % MOD;
return ansa;
}
int init(int N, int X[], int Y[]) {
time_start();
x.resize(N+1);
y.resize(N);
FOR(i,N) x[i] = X[i], y[i] = Y[i];
x[N] = 1;
yseg.N = N;
yseg.build(y);
xseg.N = N+1;
xseg.build(x);
FOR(i,N){
if(x[i]>1) xx.insert(i);
}
xx.insert(N);
xx.insert(0);
time_end();
time_start();
get_ans();
time_end();
return get_ans();
}
int cc=0;
int updateX(int pos, int val) {
cc++;
if(x[pos]==val) return get_ans();
if(val==1 && x[pos]!=1) xx.erase(pos);
else if(x[pos]==1 && val!=1) xx.insert(pos);
x[pos] = val;
xseg.update(pos, pos, x[pos]);
int anss = get_ans();
return anss;
}
int updateY(int pos, int val) {
cc++;
yseg.update(pos, pos, val);
y[pos] = val;
//cout<<"--\n";
int anss = get_ans();
return anss;
}
