#include<bits/stdc++.h>
#define pb push_back
#include "horses.h"
using namespace std;
const int maxn = 5e5 + 10;
const long long mod = 1e9 + 7;
int n, a[maxn], b[maxn];
long long t[maxn * 4], ti[maxn * 4], tg[maxn * 4];
void build(int i, int l, int r)
{
t[i] = b[l];
ti[i] = l;
tg[i] = a[l];
if(l == r)return;
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
else ti[i] = ti[2*i+1];
tg[i] = tg[2*i] * tg[2*i+1];
tg[i] %= mod;
}
int updpos, updval;
void update_prod(int i, int l, int r)
{
if(l == r)
{
tg[i] = updval;
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update_prod(2*i, l, mid);
else update_prod(2*i+1, mid+1, r);
tg[i] = tg[2*i] * tg[2*i+1];
tg[i] %= mod;
}
void update_max(int i, int l, int r)
{
if(l == r)
{
a[l] = updval;
ti[i] = l;
t[i] = a[l];
return;
}
int mid = (l + r)/2;
if(updpos <= mid)update_max(2*i, l, mid);
else update_max(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
if(t[2*i] > t[2*i+1])ti[i] = ti[2*i];
else ti[i] = ti[2*i+1];
}
int ql, qr;
int query_prod(int i, int l, int r)
{
if(l > r)return 1;
if(ql > r || qr < l)return 1;
if(ql <= l && r <= qr)return tg[i];
int mid = (l + r)/2;
int pos1 = query_prod(2*i, l, mid);
int pos2 = query_prod(2*i+1, mid+1, r);
return (pos1 * pos2) % mod;
}
int query_max(int i, int l, int r)
{
if(l > r)return 0;
if(ql > r || qr < l)return 0;
if(ql <= l && r <= qr)return ti[i];
int mid = (l + r)/2;
int pos1 = query_max(2*i, l, mid);
int pos2 = query_max(2*i+1, mid+1, r);
if(!pos1 || !pos2)return (pos1 + pos2);
if(b[pos1] > b[pos2])return pos1;
else return pos2;
}
set < int > s;
long long solve()
{
long long bestprod = 1, bestsell = 1;
long long currprod = 1, currsell = 1;
set < int >::iterator it = s.begin();
long long last= 1;
for (it = s.begin(); it != s.end(); it ++)
{
int pos = *it;
currprod *= a[pos];
ql = last;
qr = pos-1;
currsell = query_max(1, 1, n);
if(currprod > 1e9)
{
set < int >::reverse_iterator iter = s.rbegin();
ql = *iter;
qr = n;
long long csell = query_max(1, 1, n) % mod;
ql = 1;
qr = *iter;
long long cprod = query_prod(1, 1, n) % mod;
return (csell * cprod)%mod;
}
if(bestprod * bestsell < currprod * currsell)
{
bestprod = currprod;
bestsell = currsell;
}
last = pos;
// currprod *= a[pos];
}
if(bestprod * bestsell < currprod * currsell)
{
bestprod = currprod;
bestsell = currsell;
}
return (bestprod * bestsell)%mod;
}
int init(int N, int X[], int Y[])
{
n = N;
for (int i = 0; i < n; ++ i)
a[i+1] = X[i];
for (int i = 0; i < n; ++ i)
b[i+1] = Y[i];
build(1, 1, n);
for (int i = 1; i <= n; ++ i)
if(a[i] > 1)s.insert(i);
return solve();
}
int updateX(int pos, int val)
{
pos ++;
if(a[pos] > 1)s.erase(pos);
updpos = pos;
updval = val;
update_prod(1, 1, n);
if(val > 1)s.insert(pos);
return solve();
}
int updateY(int pos, int val)
{
pos ++;
b[pos] = val;
updpos = pos;
updval = val;
update_max(1, 1, n);
return solve();
}
