#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int maxn = 5e5, bit = 19;
constexpr ll mod = 1e9 + 7, siz = (1ll << bit);
using pii = pair<ll, bool>;
struct node {
ll gfac; // Growth factor
int best_pos;
bool over_mod;
};
int n;
node segtree[siz * 2] = { 0 };
ll prices[siz] = { 0 };
void fm(ll &a)
{
if (a >= mod)
{
a %= mod;
}
}
pair<ll, bool> query(int p, int l, int r, int gl, int gr)
{
if (gl > gr) assert(0);
if (l > gr || gl > r) return {1, false};
// cout << l << " " << r << "\n";
if (gl <= l && r <= gr) return {segtree[p].gfac, segtree[p].over_mod};
int mid = (l + r) >> 1;
pii le = query(p * 2, l, mid, gl, gr), ri = query(p * 2 + 1, mid + 1, r, gl, gr);
le.first *= ri.first;
le.second |= (ri.second || (le.first >= mod));
fm(le.first);
return le;
}
bool test_pos(int a, int b)
{
int swapped = 0;
if (a > b)
{
swap(a, b);
swapped = 1;
}
pii le = {prices[a], false};
pii re = query(1, 0, siz - 1, a + 1, b);
re.first *= prices[b];
re.second |= (re.first >= mod);
// cout << a << " " << b << "\t" << le.first << " " << re.first << "\n";
if (re.second) return 1 ^ swapped;
if (re.first > le.first) return 1 ^ swapped;
return 0 ^ swapped;
}
node comp(node a, const node &b)
{
a.gfac *= b.gfac;
a.over_mod |= (b.over_mod || (a.gfac >= mod));
fm(a.gfac);
return a;
}
void best_pos_comp(node &o, node &a, node &b)
{
// cout << a.best_pos << " " << b.best_pos << "\n";
if (test_pos(a.best_pos, b.best_pos))
{
o.best_pos = b.best_pos;
} else {
o.best_pos = a.best_pos;
}
}
ll get_val_pos(int p)
{
ll out = query(1, 0, siz - 1, 0, p).first * prices[p];
fm(out);
return out;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; i++)
{
prices[i] = Y[i];
segtree[i + siz] = node{X[i], i, false};
}
for (int i = n; i < siz; i++)
{
segtree[i + siz] = node{1, i, false};
}
// for (int i = 1; i < siz * 2; i++)
// {
// if (__builtin_popcount(i) == 1) cout << "\n";
// cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
// }
// cout << "\n";
for (int i = siz - 1; i > 0; i--)
{
segtree[i] = comp(segtree[i * 2], segtree[i * 2 + 1]);
}
// for (int i = 1; i < siz * 2; i++)
// {
// if (__builtin_popcount(i) == 1) cout << "\n";
// cout << segtree[i].gfac << " " << segtree[i].best_pos << "\t";
// }
// cout << "\n";
for (int i = siz - 1; i > 0; i--)
{
best_pos_comp(segtree[i], segtree[i * 2], segtree[i * 2 + 1]);
}
return (int)get_val_pos(segtree[1].best_pos);
}
void update_upwards(ll p)
{
p += siz;
while (p > 1)
{
p /= 2;
segtree[p] = comp(segtree[p * 2], segtree[p * 2 + 1]);
best_pos_comp(segtree[p], segtree[p * 2], segtree[p * 2 + 1]);
}
}
int updateX(int pos, int val) {
segtree[pos + siz].gfac = val;
update_upwards(pos);
return (int)get_val_pos(segtree[1].best_pos);
}
int updateY(int pos, int val) {
prices[pos] = val;
update_upwards(pos);
return (int)get_val_pos(segtree[1].best_pos);
}
