#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e5 + 20;
const int mod = 1e9 + 7;
int maxy[maxn * 4] , mulx[maxn * 4] , n;
int x[maxn] , y[maxn];
set<int> st;
void updx(int p , int val , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
mulx[v] = val;
return;
}
int m = (s + e) / 2;
if(p < m)
updx(p , val , s , m , 2 * v);
else
updx(p , val , m , e , 2 * v + 1);
mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
}
void updy(int p , int val , int s = 0 , int e = n , int v = 1)
{
if(e - s < 2)
{
maxy[v] = val;
return;
}
int m = (s + e) / 2;
if(p < m)
updy(p , val , s , m , 2 * v);
else
updy(p , val , m , e , 2 * v + 1);
maxy[v] = max(maxy[2 * v] , maxy[2 * v + 1]);
}
int getx(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return mulx[v];
else if(r <= s || e <= l)
return 1;
int m = (s + e) / 2;
return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
}
int gety(int l , int r , int s = 0 , int e = n , int v = 1)
{
if(l <= s && e <= r)
return maxy[v];
if(r <= s || e <= l)
return 0;
int m = (s + e) / 2;
return max(gety(l , r , s , m , 2 * v) , gety(l , r , m , e , 2 * v + 1));
}
void ux(int p , int val)
{
if(x[p] > 1)
st.erase(p);
x[p] = val;
updx(p , val);
if(x[p] > 1)
st.insert(p);
}
int solve()
{
vector<int> tmp;
for(auto it = st.end(); it != st.begin() && tmp.size() < 35;)
{
it--;
tmp.pb(*it);
}
if(tmp.empty())
return gety(0 , n);
reverse(tmp.begin() , tmp.end());
int m = tmp.size();
tmp.pb(n);
vector<int> y;
for(int i = 0; i < m; i++)
y.pb(gety(tmp[i] , tmp[i + 1]));
for(int i = 0; i < m; i++)
{
bool good = 1;
int mul = 1;
for(int j = i + 1; j < m && good; j++)
{
mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]);
if(y[i] < 1LL * mul * y[j])
good = 0;
}
if(good)
return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod;
}
return -1;
}
int init(int N, int X[], int Y[])
{
n = N;
for(int i = 0; i < n; i++)
{
ux(i , X[i]);
updy(i , Y[i]);
}
return solve();
}
int updateX(int pos, int val)
{
ux(pos , val);
return solve();
}
int updateY(int pos, int val)
{
updy(pos , val);
return solve();
}
