#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod(1000000007);
struct Nod { int prefix = 1 , sufix = 1 , indice_maxim = 0 , maxim = 0 , total = 1; } arbore[1000000];
int lungime , factor_1[500001] , factor_2[500001];
inline void Combina (Nod& rezultat , Nod& stanga , Nod& dreapta)
{
rezultat.total = 1LL * stanga.total * dreapta.total % mod;
if (factor_2[stanga.indice_maxim] > min(1000000001LL , min(1000000001LL , 1LL * stanga.sufix * factor_2[dreapta.indice_maxim]) * dreapta.prefix))
{
rezultat.prefix = stanga.prefix;
rezultat.sufix = min(1000000001LL , min(1000000001LL , 1LL * stanga.sufix * dreapta.prefix) * dreapta.sufix);
rezultat.indice_maxim = stanga.indice_maxim;
rezultat.maxim = stanga.maxim;
}
else
{
rezultat.prefix = min(1000000001LL , min(1000000001LL , 1LL * stanga.prefix * dreapta.sufix) * dreapta.prefix);
rezultat.sufix = dreapta.sufix;
rezultat.indice_maxim = dreapta.indice_maxim;
rezultat.maxim = 1LL * stanga.total * dreapta.maxim % mod;
}
}
inline void Build (const int nod , const int stanga , const int dreapta)
{
if (stanga == dreapta)
{
arbore[nod].prefix = factor_1[stanga];
arbore[nod].sufix = 1;
arbore[nod].indice_maxim = stanga;
arbore[nod].maxim = 1LL * factor_1[stanga] * factor_2[stanga] % mod;
arbore[nod].total = factor_1[stanga];
return;
}
const int mijloc = (stanga + dreapta) >> 1;
Build(nod + 1 , stanga , mijloc);
Build(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta);
Combina(arbore[nod] , arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}
inline void Update (const int nod , const int stanga , const int dreapta , const int indice)
{
if (stanga == dreapta)
{
arbore[nod].prefix = factor_1[stanga];
arbore[nod].sufix = 1;
arbore[nod].indice_maxim = stanga;
arbore[nod].maxim = 1LL * factor_1[stanga] * factor_2[stanga] % mod;
arbore[nod].total = factor_1[stanga];
return;
}
const int mijloc = (stanga + dreapta) >> 1;
if (indice <= mijloc) { Update(nod + 1 , stanga , mijloc , indice); }
else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice); }
Combina(arbore[nod] , arbore[nod + 1] , arbore[nod + ((mijloc - stanga + 1) << 1)]);
}
int init (int __lungime , int __factor_1[] , int __factor_2[])
{
lungime = __lungime;
for (int indice = 1 ; indice <= lungime ; indice++)
{ factor_1[indice] = __factor_1[indice - 1]; factor_2[indice] = __factor_2[indice - 1]; }
Build(1 , 1 , lungime);
return arbore[1].maxim;
}
int updateX (int indice , int valoare)
{
factor_1[indice + 1] = valoare;
Update(1 , 1 , lungime , indice + 1);
return arbore[1].maxim;
}
int updateY (int indice , int valoare)
{
factor_2[indice + 1] = valoare;
Update(1 , 1 , lungime , indice + 1);
return arbore[1].maxim;
}
