#include "horses.h"
#include <set>
#include <vector>
#include <algorithm>
///set pe platouri pe X => rangeuri de forma F 1 1 1 ... 1
///in ficare set tinem: l, r, F, maxY
///arbore de intervale peste Y
///update Y => update in arborele de intervale
///arbore de intervale peste X
///update X => update in arborele de intervale
///update X => 4 cazuri:
///1) nicio modificare
///2) un F > 1 devine 1 => unim intervalul curent cu cel din stanga
///2) un F = 1 devine >1 => separam intervalul curent in 2 intervale mai mici
///3) un F > 1 se modifica => modificam F in setul respectiv
const int YMAX = 1e9;
const int MOD = 1e9 + 7;
const int NMAX = 5e5;
int n, x[NMAX + 2], y[NMAX + 2];
struct Aintx {
long long v[4 * NMAX];
void Build(int node, int st, int dr)
{
if(st == dr)
{
v[node] = x[st];
return ;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
}
void setx(int node, int st, int dr, int pos, int val)
{
if(st == dr)
{
v[node] = val;
return;
}
int mid = (st + dr) >> 1;
if(pos <= mid)
setx(2 * node, st, mid, pos, val);
else
setx(2 * node + 1, mid + 1, dr, pos, val);
v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
}
long long queryx(int node, int st, int dr, int l, int r)
{
if(l <= st && dr <= r)
return v[node];
if(dr < l || st > r)
return 1;
int mid = (st + dr) >> 1;
long long ans1 = queryx(2 * node, st, mid, l, r);
long long ans2 = queryx(2 * node + 1, mid + 1, dr, l, r);
return (1LL * ans1 * ans2) % MOD;
}
};
Aintx aintx;
struct Ainty {
long long v[4 * NMAX];
void Build(int node, int st, int dr)
{
if(st == dr)
{
v[node] = y[st];
return ;
}
int mid = (st + dr) >> 1;
Build(2 * node, st, mid);
Build(2 * node + 1, mid + 1, dr);
v[node] = std::max(v[2 * node], v[2 * node + 1]);
}
void sety(int node, int st, int dr, int pos, int val)
{
if(st == dr)
{
v[node] = val;
return;
}
int mid = (st + dr) >> 1;
if(pos <= mid)
sety(2 * node, st, mid, pos, val);
else
sety(2 * node + 1, mid + 1, dr, pos, val);
v[node] = std::max(v[2 * node], v[2 * node + 1]);
}
long long queryy(int node, int st, int dr, int l, int r)
{
if(l <= st && dr <= r)
return v[node];
if(dr < l || st > r)
return 0;
int mid = (st + dr) >> 1;
int ans1 = queryy(2 * node, st, mid, l, r);
int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);
return std::max(ans1, ans2);
}
};
Ainty ainty;
struct Interval {
int st, dr;
long long f, maxy;
bool operator < (const Interval other) const {
return st < other.st;
}
};
std::set < Interval > s;
long long Query()
{
auto p = s.rbegin();
std::vector <int> xs;
std::vector <int> ys;
std::vector <std::pair <int, int>> segments;
int seenSegments = 0;
long long xProd = 1LL;
while(true)
{
Interval i = *p;
--p;
xProd *= i.f;
if(xProd > YMAX)
break;
xs.push_back(i.f);
ys.push_back(i.maxy);
segments.push_back({i.st, i.dr});
seenSegments++;
if(seenSegments == (int)s.size())
break;
}
reverse(xs.begin(), xs.end());
reverse(ys.begin(), ys.end());
reverse(segments.begin(), segments.end());
long long currX = 1LL, currMaxProd = 1LL;
std::pair <int, int> maxSegment;
for(int i = 0; i < (int)xs.size(); i++)
{
currX *= xs[i];
if(1LL * currX * ys[i] > currMaxProd)
{
currMaxProd = 1LL * currX * ys[i];
maxSegment = segments[i];
}
}
return (1LL * aintx.queryx(1, 0, n - 1, 0, maxSegment.second) * ainty.queryy(1, 0, n - 1, maxSegment.first, maxSegment.second)) % MOD;
}
int init(int N, int X[], int Y[]) {
n = N;
for(int i = 0; i < n; i++)
x[i] = X[i], y[i] = Y[i];
aintx.Build(1, 0, n - 1);
ainty.Build(1, 0, n - 1);
int l = 0, factor = x[0];
for(int r = 1; r < n; r++)
if(x[r] > 1)
{
Interval i;
i.st = l;
i.dr = r - 1;
i.f = factor;
i.maxy = ainty.queryy(1, 0, n - 1, l, r - 1);
s.insert(i);
l = r;
factor = x[r];
}
Interval i;
i.st = l;
i.dr = n - 1;
i.f = factor;
i.maxy = ainty.queryy(1, 0, n - 1, l, n - 1);
s.insert(i);
return Query();
}
int updateX(int pos, int val) {
if(x[pos] == val)
return Query();
aintx.setx(1, 0, n - 1, pos, val);
auto p = s.upper_bound({pos, 0, 0, 0});
Interval bef = *(--p);
if(x[pos] > 1 && val == 1)
{
Interval bef_bef = *(--p);
Interval merged;
merged.st = bef_bef.st;
merged.dr = bef.dr;
merged.f = bef_bef.f;
merged.maxy = ainty.queryy(1, 0, n - 1, merged.st, merged.dr);
s.erase(bef);
s.erase(bef_bef);
s.insert(merged);
}
else if(x[pos] == 1 && val > 1)
{
Interval split1, split2;
split1.st = bef.st;
split1.dr = pos - 1;
split1.f = bef.f;
split1.maxy = ainty.queryy(1, 0, n - 1, bef.st, pos - 1);
split2.st = pos;
split2.dr = bef.dr;
split2.f = val;
split2.maxy = ainty.queryy(1, 0, n - 1, pos, bef.dr);
s.erase(bef);
s.insert(split1);
s.insert(split2);
}
else
{
s.erase(bef);
bef.f = val;
s.insert(bef);
}
return Query();
}
int updateY(int pos, int val) {
ainty.sety(1, 0, n - 1, pos, val);
auto p = s.upper_bound({pos, 0, 0, 0});
Interval bef = *(--p);
s.erase(bef);
s.insert({bef.st, bef.dr, bef.f, ainty.queryy(1, 0, n - 1, bef.st, bef.dr)});
return Query();
}
