#include "horses.h"
#include <algorithm>
using namespace std;
int N,nn;
int next[500002],before[500002];
long long ans,mulx;
long long x[500002],y[500002];
long long seg[2000000];
#define MOD 1000000007
long long inv(long long value){
if(value == 1) return 1;
long long tmp = ((inv(MOD%value)*((-MOD)/value)));
tmp %= MOD;
if(tmp < 0) tmp += MOD;
return tmp;
}
void update(int node,long long value){
seg[node] = value;
node /= 2;
while(node > 0){
seg[node] = max(seg[node*2],seg[(node*2)+1]);
node /= 2;
}
}
int s,e;
long long big;
void finding(int node,int left,int right){
if(e < left || right < s) return;
if(s <= left && right <= e){
big = max(big,seg[node]);
return;
}
int mid = (left+right)/2;
finding(node*2,left,mid);
finding((node*2)+1,mid+1,right);
}
long long get(){
big = 0;
finding(1,1,nn);
return big;
}
long long print[50];
void process(){
int i,t,cnt;
long long tmp;
ans = 0; tmp = 1; cnt = 0;
t = next[N+1];
while(t != 0){
s = t; e = before[t]-1;
print[++cnt] = get();
tmp *= x[t];
if(tmp >= 1000000000) break;
t = next[t];
}
if(t == 0){
s = 1; e = before[0]-1;
if(s <= e){
ans = get();
}
tmp = 1; t = before[0];
for(i=cnt; i>=1; i--){
tmp *= x[t];
ans = max(ans,tmp*print[i]);
t = before[t];
}
}else{
for(i=cnt; i>=1; i--){
}
}
}
int init(int n, int X[], int Y[]) {
int i,t;
mulx = 1;
for(i=1; i<=n; i++){
x[i] = (long long)X[i-1];
mulx *= x[i]; mulx %= MOD;
y[i] = (long long)Y[i-1];
}
N = n;
for(nn=1; nn<N; nn*=2);
for(i=1; i<=N; i++) update(nn+i-1,y[i]);
t = N+1;
for(i=N; i>=1; i--){
if(x[i] > 1){
before[i] = t;
next[t] = i;
t = i;
}
}
before[0] = t;
process();
return (int)ans;
}
int updateX(int pos, int val) {
pos++;
mulx *= inv(x[pos]); mulx %= MOD;
mulx *= (long long)val; mulx %= MOD;
if(x[pos] == 1 && val > 1){
}else if(x[pos] > 1 && val == 1){
}
x[pos] = (long long)val;
process();
return (int)ans;
}
int updateY(int pos, int val) {
update(nn+pos,val);
process();
return (int)ans;
}
