#include "horses.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
long long mod = 1e9 + 7;
class segtree
{
public:
int l;
int r;
long long mx;
long long p;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
mx = p = 1;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
long long rangemax(int L, int R)
{
if(R < l || r < L) return 0;
if(L <= l && r <= R) return mx;
return max(left->rangemax(L, R), right->rangemax(L, R));
}
long long rangeprod(int L, int R)
{
if(R < l || r < L) return 1;
if(L <= l && r <= R) return p;
return (left->rangeprod(L, R) * right->rangeprod(L, R)) % mod;
}
void update(int I, long long V)
{
if(I < l || r < I) return;
if(l == r) mx = p = V;
else
{
left->update(I, V);
right->update(I, V);
mx = max(left->mx, right->mx);
p = (left->p * right->p) % mod;
}
}
};
struct growth
{
int i;
long long x;
};
bool operator < (growth A, growth B)
{
return A.i > B.i;
}
int N;
segtree X;
segtree Y;
set<growth> Xset;
int compute()
{
long long fullprod = 1;
int fullprod_pos = N;
for(growth g: Xset)
{
if(fullprod * g.x >= 1e9)
{
fullprod_pos = g.i + 1;
break;
}
fullprod *= g.x;
fullprod_pos = g.i;
} //fullprod_pos is the leftmost position such that Xproduct(fullprod_pos, N-1) < 1e9
//The leftmost selling point is fullprod_pos - 1
long long res = 1;
int res_pos = 0;
for(growth g: Xset)
{
if(g.i < fullprod_pos - 1) break;
if(X.rangeprod(fullprod_pos - 1, g.i) * Y.rangemax(g.i, N-1) > res)
{
res = X.rangeprod(fullprod_pos - 1, g.i) * Y.rangemax(g.i, N-1);
res_pos = g.i;
}
}
return int( (X.rangeprod(0, res_pos) * Y.rangemax(res_pos, N-1)) % mod );
}
int init(int n, int x[], int y[])
{
N = n;
X = segtree(0, N);
Y = segtree(0, N);
for(int i = 0; i < N; i++)
{
X.update(i, x[i]);
Y.update(i, y[i]);
if(x[i] != 1) Xset.insert(growth{i, x[i]});
}
X.update(N, 1);
Y.update(N, 0);
Xset.insert(growth{N, 1});
return compute();
}
int updateX(int pos, int val)
{
X.update(pos, val);
Xset.erase(growth{pos, val});
if(val != 1) Xset.insert(growth{pos, val});
// cout << "after update: \n";
// for(int i = 0; i < N; i++) cout << X.rangemax(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
// cout << '\n';
return compute();
}
int updateY(int pos, int val)
{
Y.update(pos, val);
// cout << "after update: \n";
// for(int i = 0; i < N; i++) cout << X.rangemax(i, i) << ' ';
// cout << '\n';
// for(int i = 0; i < N; i++) cout << Y.rangemax(i, i) << ' ';
// cout << '\n';
return compute();
}
