#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5e5+5;
const int mod = 1e9+7;
ll n;
set<ll> st;
pair<ll, ll> seg[MAX_N*4];
ll x[MAX_N+5];
ll y[MAX_N+5];
void upd(ll v, ll l, ll r, ll ix, pair<ll, ll> tr)
{
if (l == r)
{
seg[v] = tr;
return;
}
ll mid = (l + r) / 2;
if (ix <= mid)
upd(v*2+1, l, mid, ix, tr);
else if (ix > mid)
upd(v*2+2, mid+1, r, ix, tr);
seg[v].second = max(seg[v*2+2].second, seg[v*2+1].second);
seg[v].first = seg[v*2+1].first*seg[v*2+2].first%mod;
}
pair<ll, ll> qr(ll v, ll l, ll r, ll i, ll j)
{
if (l > r || i > j)
return {1, 0};
if (i <= l && j >= r)
return seg[v];
ll mid = (l + r) / 2;
pair<ll, ll> lv = qr(v*2+1, l, mid, i, min(j, mid));
pair<ll, ll> ds = qr(v*2+2, mid+1, r, max(i, mid+1), j);
return {lv.first*ds.first, max(lv.second, ds.second)};
}
ll getMax()
{
pair<ll, ll> t = qr(0, 0, n-1, 0, n-1);
ll rez = t.first*y[n-1]%mod;
ll j = n-1, pry = y[n-1];
vector<ll> zac;
for (ll i = 0; i < 30 && st.size(); i++)
{
zac.push_back(*st.rbegin());
ll tj = *st.rbegin();
st.erase(tj);
t = qr(0, 0, n-1, tj+1, j);
if (t.first >= mod)
break;
if (t.first*pry < t.second)
{
j = tj;
pry = t.second;
t = qr(0, 0, n-1, 0, j);
rez = t.first*pry;
}
}
for (ll v : zac)
st.insert(v);
return rez%mod;
}
int init(int N, int X[], int Y[])
{
n = N;
for (ll i = 0; i < n; i++)
{
x[i] = X[i]; y[i] = Y[i];
if (X[i] != 1)
st.insert(i);
upd(0, 0, n-1, i, {X[i], Y[i]});
}
return getMax();
}
int updateX(int pos, int val)
{
if (st.count(pos))
st.erase(pos);
else
st.insert(pos);
x[pos] = val;
upd(0, 0, n-1, pos, {x[pos], y[pos]});
return getMax();
}
int updateY(int pos, int val)
{
y[pos] = val;
upd(0, 0, n-1, pos, {x[pos], y[pos]});
return getMax();
}
