#include <bits/stdc++.h>
#include "horses.h"
#define DIMN 500010
#define MOD 1000000007
using namespace std;
int nt , xt[DIMN] , yt[DIMN];
set < pair < pair <int , int> , pair <int , int> > > state;
set < pair < pair <int , int> , pair <int , int> > > :: iterator aux , it;
set < pair < pair <int , int> , pair <int , int> > > :: reverse_iterator rit;
int aint[4*DIMN] , prod[4 * DIMN];
void build (int nod , int st , int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = st;
prod[nod] = xt[st];
return;
}
build (2 * nod , st , mid);
build (2 * nod + 1 , mid + 1 , dr);
if (yt[aint[2 * nod]] > yt[aint[2 * nod + 1]])
aint[nod] = aint[2 * nod];
else aint[nod] = aint[2 * nod + 1];
prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;
}
void update_prod (int nod , int st , int dr , int pos , int val){
int mid = (st + dr)/2;
if (st == dr){
prod[nod] = val;
return;
}
if (pos <= mid)
update_prod(2 * nod , st , mid , pos , val);
else
update_prod(2 * nod + 1 , mid + 1 , dr , pos , val);
prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;
}
int query (int nod , int st , int dr , int x , int y){
int mid = (st + dr)/2 , maxi = 0 , val;
if (x <= st && dr <= y){
return aint[nod];
}
if (x <= mid){
val = query(2 * nod , st , mid , x , y);
if (maxi == 0 || yt[maxi] < yt[val])
maxi = val;
}
if (mid + 1 <= y){
val = query(2 * nod + 1 , mid + 1 , dr , x , y);
if (maxi == 0 || yt[maxi] < yt[val])
maxi = val;
}
return maxi;
}
int query_prod (int nod , int st , int dr , int x , int y){
int mid = (st + dr)/2 , sol = 1;
if (x <= st && dr <= y){
return prod[nod];
}
if (x <= mid)
sol = (1LL * sol * query_prod(2 * nod , st , mid , x , y))%MOD;
if (mid + 1 <= y)
sol = (1LL * sol * query_prod(2 * nod + 1 , mid + 1 , dr , x , y))%MOD;
return sol;
}
void update (int nod , int st , int dr , int pos , int val){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = pos;
return;
}
if (pos <= mid)
update(2 * nod , st , mid , pos , val);
else
update(2 * nod + 1 , mid + 1 , dr , pos , val);
if (yt[aint[2 * nod]] > yt[aint[2 * nod + 1]])
aint[nod] = aint[2 * nod];
else aint[nod] = aint[2 * nod + 1];
}
int solve_current_state (){
int have_sol , idx , inc , ymax , taken;
/// !! solutia e in ultimele 60 de pozitii
have_sol = 0;
idx = 0;
for (rit = state.rbegin() , taken = 1 ; rit != state.rend() && taken <= 60; rit++ , taken++){
inc = (*rit).first.first;
ymax = (*rit).second.second;
if (have_sol == 0){
have_sol = 1LL * xt[inc] * yt[ymax];
idx = ymax;
}
else {
if (yt[ymax] < have_sol){
if (have_sol <= 1000000000)
have_sol = (have_sol * xt[ymax]);
}
else {
have_sol = 1LL * xt[inc] * yt[ymax];
idx = ymax;
}
}
}
return (1LL * query_prod (1 , 0 , nt - 1 , 0 , idx) * yt[idx])%MOD;
}
int init(int n, int x[], int y[]){
int i , inc , sf , ymax;
nt = n;
for (i = 0 ; i < n ; i++){
xt[i] = x[i];
yt[i] = y[i];
}
for (i = 0 ; i < n ; i++){
if (x[i] != 1){
state.insert(make_pair( make_pair(i , i) , make_pair(x[i] , i) ));
}
else {
inc = i;
sf = i;
ymax = i;
while (sf + 1 < n && x[sf + 1] == 1){
if (y[ymax] < y[sf + 1])
ymax = sf + 1;
sf++;
}
state.insert(make_pair( make_pair(inc , sf) , make_pair(1 , ymax) ));
i = sf;
}
}
build (1 , 0 , nt - 1);
return solve_current_state();
}
int updateX(int pos, int val){
int inc , sf , vcurr , ymax , inc2 , sf2 , ymax2;
it = state.upper_bound(make_pair ( make_pair(pos , nt) , make_pair(0 , 0) ));
it--;
inc = (*it).first.first;
sf = (*it).first.second;
vcurr = (*it).second.first;
ymax = (*it).second.second;
if (val == 1){ /// cazul cand poate se prelungeste un interval de 1
/// , sau se form unul nou
if (vcurr != 1){
vcurr = 1;
aux = it;
aux--;
if (it != state.begin() && (*aux).second.first == 1){ /// aux exista
/// ai un interval de 1 la stanga
inc2 = (*aux).first.first;
sf2 = (*aux).first.second;
ymax2 = (*aux).second.second;
if (yt[ymax] < yt[ymax2])
ymax = ymax2;
inc = inc2;
state.erase(aux);
}
aux = it;
aux++;
if (aux != state.end() && (*aux).second.first == 1){
/// ai un interval de 1 la dreapta
inc2 = (*aux).first.first;
sf2 = (*aux).first.second;
ymax2 = (*aux).second.second;
if (yt[ymax] < yt[ymax2])
ymax = ymax2;
sf = sf2;
state.erase(aux);
}
state.erase(it);
state.insert(make_pair( make_pair(inc , sf) , make_pair(1 , ymax) ));
}
}
else { /// cazul cand se destrama un interval de 1, sau doar se updateaza o val
if (vcurr != 1){ /// se updateaza o valoare normala
state.erase(it);
state.insert(make_pair( make_pair(inc , sf) , make_pair(val , ymax) ));
}
else { /// se destrama un interval
state.erase(it);
state.insert(make_pair( make_pair(pos , pos) , make_pair(val , pos) ));
if (inc < pos){
ymax = query (1 , 0 , nt - 1 , inc , pos - 1);
state.insert(make_pair( make_pair(inc , pos - 1) , make_pair(1 , ymax) ));
}
if (pos < sf){
ymax = query (1 , 0 , nt - 1 , pos + 1 , sf);
state.insert(make_pair( make_pair(pos + 1 , sf) , make_pair(1 , ymax) ));
}
}
}
xt[pos] = val;
return solve_current_state();
}
int updateY(int pos, int val){
yt[pos] = val;
update (1 , 0 , nt , pos , val);
return solve_current_state();
}
