#include "horses.h"
#include <bits/stdc++.h>
#define MAX_N 500000
#define MOD 1000000007
#define INF 1000000000
#define debug 0
using namespace std;
int segtree[4*MAX_N], N;
long long X[MAX_N], Y[MAX_N];
long long partX[4*MAX_N];
struct classcomp {
bool operator() (const int& lhs, const int& rhs) const
{return lhs>rhs;}
};
set<int, classcomp> S;//Skup indexa na kojima X[i]>1
int rmq(int ql, int qr){//Vraca index!!!
//printf("rmq(%d, %d)\n", ql, qr);
int max=0, indmax=-1;
for(int i=ql; i<qr; ++i){
if(Y[i]>max){
max=Y[i];
indmax=i;
}
}
return indmax;
//return query(ql, qr, 0, N, 0);
}
int partXX(int pos){
long long ret=1;
for(int i=0; i<pos+1; ++i){
ret*=X[i];
if(ret>MOD)ret%=MOD;
}
return ret;
//return partquery(0, pos+1, 0, N, 0);
}
vector<int> big;//Indexi svih X-eva koji su veci od 1
int num_big=0;
int solve(){
big.clear();//Moze brze
long long pi=1;
for(auto i:S){
pi*=X[i];
big.push_back(i);
if(pi>INF)break;
}
if(pi<INF)big.push_back(0);
reverse(big.begin(), big.end());
/*if(pi<INF){
big.clear();
big.push_back(0);
for(auto i:S){
big.push_back(i);
}
}*/
pi=1;
int d=big.size();
if(debug){
for(int i=0; i<d; ++i)printf("%d ", big[i]);
printf("\n");
}
long long totmax=0, indmax=-1;
for(int i=0; i<d; ++i){
long long maxy;
if(i!=d-1){
maxy=rmq(big[i], big[i+1]);
}
else {
maxy=rmq(big[i], N);
//printf("ovde\n");
}
if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
if(i!=0)pi*=X[big[i]];
if((long long)Y[maxy]*pi>totmax){
totmax=(long long)Y[maxy]*pi;
indmax=maxy;
}
}
if(debug){
printf("totmax=%d, indmax=%d\n", totmax, indmax);
printf("partXX(indmax)=%d\n", partXX(indmax));
}
long long res=(long long)Y[indmax]*partXX(indmax);
return res%MOD;
}
int init(int n, int x[], int y[]) {
N=n;
for(int i=0; i<N; ++i){
X[i]=x[i];
Y[i]=y[i];
if(X[i]>1){
S.insert(i);
}
}
//maketree(0, N, 0);
if(debug){
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, i);
}
printf("\n");
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, segtree[i]);
}
printf("\n");
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, partX[i]);
}
printf("\n");
}
return solve();
}
int updateX(int pos, int val) {
if(X[pos]==1 && val>1){
S.insert(pos);
X[pos]=val;
//updatepart(0, N, 0, pos);
}
else if(X[pos]>1 && val==1){
S.erase(pos);
X[pos]=1;
//updatepart(0, N, 0, pos);
}
else if(X[pos]>1 && val>1){
X[pos]=val;
//updatepart(0, N, 0, pos);
}
return solve();
}
int updateY(int pos, int val) {
Y[pos]=val;
//updatetree(0, N, 0, pos);
return solve();
}
