#include<iostream>
#include<set>
#include "horses.h"
#define DIM 500005
#define mod 1000000007
#define f first
#define s second
using namespace std;
static int n;
static int x[DIM], y[DIM], lst[DIM];
static pair<int, int> aint[4 * DIM], aux;
static set< pair<int, int> > w;
static void build(int nod, int st, int dr){
if(st == dr){
aint[nod] = make_pair(x[st], y[st]);
}
else{
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
aint[nod].s = max(aint[2 * nod].s, aint[2 * nod + 1].s);
}
}
static void update(int nod, int st, int dr, int p){
if(st == dr){
aint[nod] = make_pair(x[st], y[st]);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p);
}
else{
update(2 * nod + 1, mid + 1, dr, p);
}
aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
aint[nod].s = max(aint[2 * nod].s, aint[2 * nod + 1].s);
}
}
static void query(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
aux.f = aux.f * 1LL * aint[nod].f % mod;
aux.s = max(aux.s, aint[nod].s);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
query(2 * nod, st, mid, p, u);
}
if(u > mid){
query(2 * nod + 1, mid + 1, dr, p, u);
}
}
}
static int solve(){
int i, ind, ymax;
long long val, sol;
set< pair<int, int> > :: iterator it;
val = 1;
it = w.end();
it--;
for(; it != w.begin(); it--){
val *= x[ it->f ];
if(val > 1000000000){
break;
}
}
val = 1;
sol = ymax = y[ it->f ];
ind = it->f;
it++;
for(; it != w.end(); it++){
val *= x[ it->f ];
aux = make_pair(1, 0);
query(1, 1, n, it->f, it->s);
if(sol < val * aux.s){
sol = val * aux.s;
ymax = aux.s;
ind = it->s;
}
}
aux = make_pair(1, 0);
query(1, 1, n, 1, ind);
return aux.f * 1LL * ymax % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
w.insert( make_pair(0, 0) );
int lst;
for(int i = 1; i <= n; i++){
x[i] = X[i - 1];
y[i] = Y[i - 1];
if(x[i] != 1){
w.insert( make_pair(i, i) );
}
else{
if(x[i - 1] != 1){
lst = i;
}
if(x[i + 1] != 1){
w.insert( make_pair(lst, i) );
}
}
}
build(1, 1, n);
return solve();
}
int updateX(int pos, int val) {
pos++;
set< pair<int, int> > :: iterator it;
pair<int, int> a;
if(x[pos] == 1){
it = w.lower_bound( make_pair(pos + 1, 0) );
it--;
a = *it;
w.erase(it);
if(a.f != pos){
w.insert( make_pair(a.f, pos - 1) );
}
if(a.s != pos){
w.insert( make_pair(pos + 1, a.s) );
}
w.insert( make_pair(pos, pos) );
}
x[pos] = val;
update(1, 1, n, pos);
if(x[pos] == 1){
w.erase( make_pair(pos, pos) );
a = make_pair(pos, pos);
if(x[pos - 1] == 1){
it = w.lower_bound( make_pair(pos, pos) );
it--;
a.f = it->f;
w.erase(it);
}
if(x[pos + 1] == 1){
it = w.lower_bound( make_pair(pos, pos) );
a.s = it->s;
w.erase(it);
}
w.insert(a);
}
return solve();
}
int updateY(int pos, int val) {
pos++;
y[pos] = val;
update(1, 1, n, pos);
return solve();
}
