#include "horses.h"
#include <stdio.h>
#include <algorithm>
#include <set>
const int MOD = 1000000007;
const int MAX_N = 500000;
int N;
int X[MAX_N];
long long allProdX = 1;
long long power(long long base, int exp) {
if (exp == 1) {
return base;
} else if (exp % 2 == 0) {
return power(base * base % MOD, exp / 2);
} else {
return power(base, exp - 1) * base % MOD;
}
}
int inv(int value) {
return (int)power(value, MOD - 2);
}
struct Index {
int index;
int maxRangeY;
};
bool operator < (const Index &a, const Index &b) {
return a.index < b.index;
}
int segTreeN = 1 << 19;
int segTree[1 << 20];
void segTreeUpdate(int index, int newValue) {
index += segTreeN;
segTree[index] = newValue;
while (index > 1) {
index /= 2;
segTree[index] = std::max(segTree[2 * index], segTree[2 * index + 1]);
}
}
int segTreeRangeMax(int left, int right) {
right++;
left += segTreeN;
right += segTreeN;
int answer = 0;
while (left < right) {
if (left % 2 == 1) {
answer = std::max(answer, segTree[left]);
left++;
}
if (right % 2 == 1) {
right--;
answer = std::max(answer, segTree[right]);
}
left /= 2;
right /= 2;
}
return answer;
}
std::set<Index> relevantXs;
struct Fraction {
int x;
int y;
};
bool operator <(const Fraction &a, const Fraction &b) {
// return a.x / a.y < b.x / b.y;
return (long long)a.x * b.y < (long long)b.x * a.y;
}
int query() {
Fraction answer = Fraction{1, 1};
long long productX = 1;
auto it = relevantXs.rbegin();
while (it != relevantXs.rend() && productX < MOD) {
answer = std::max(answer, Fraction{it->maxRangeY, (int)productX});
productX *= X[it->index];
it++;
}
//printf("%lld %d %d\n", allProdX, answer.x, answer.y);
return int(allProdX * answer.x % MOD * inv(answer.y) % MOD);
}
int init(int n, int x[], int y[]) {
int maxY = 0;
N = n;
for (int i = N - 1; i >= 0; i--) {
X[i] = x[i];
allProdX = allProdX * X[i] % MOD;
segTreeUpdate(i, y[i]);
maxY = std::max(maxY, y[i]);
if (X[i] > 1 || i == 0) {
relevantXs.insert(Index{i, maxY});
maxY = 0;
}
}
return query();
}
void dump() {
for (Index index : relevantXs) {
printf("(%d, %d) ", index.index, index.maxRangeY);
}
}
int updateX(int pos, int val) {
//printf("updateX(%d, %d)\n", pos, val);
allProdX = allProdX * inv(X[pos]) % MOD;
if (pos > 0 && X[pos] > 1) {
// removeX(pos);
//printf("removeX(%d) ", pos);
//fflush(stdout);
auto it = relevantXs.find(Index{pos, 0});
//printf("done (%d, %d)!\n", it->index, it->maxRangeY);
//fflush(stdout);
int maxY2 = it->maxRangeY;
auto prevIt = prev(it);
//printf("done (%d, %d)!\n", it->index, it->maxRangeY);
//fflush(stdout);
relevantXs.erase(it);
//printf("done!\n");
//fflush(stdout);
int maxY1 = prevIt->maxRangeY;
int previousIndex = prevIt->index;
relevantXs.erase(prevIt);
//printf("done!\n");
//fflush(stdout);
relevantXs.insert(Index{previousIndex, std::max(maxY1, maxY2)});
//printf("done!\n");
//fflush(stdout);
}
X[pos] = val;
allProdX = allProdX * X[pos] % MOD;
if (pos > 0 && X[pos] > 1) {
// insertX(pos);
//printf("insertX(%d) ", pos);
//fflush(stdout);
int rightIndex, leftIndex;
auto it = relevantXs.lower_bound(Index{pos, 0});
if (it == relevantXs.end()) {
rightIndex = N - 1;
} else {
rightIndex = it->index - 1;
}
auto prevIt = prev(it);
leftIndex = prevIt->index;
relevantXs.erase(prevIt);
relevantXs.insert(Index{leftIndex,
segTreeRangeMax(leftIndex, pos - 1)});
relevantXs.insert(Index{pos,
segTreeRangeMax(pos, rightIndex)});
//printf("done!\n");
//fflush(stdout);
}
//dump();
return query();
}
int updateY(int pos, int val) {
//printf("updateY(%d, %d)\n", pos, val);
segTreeUpdate(pos, val);
long long productX = 1;
int prevIndex = N;
auto it = relevantXs.end();
it--;
while (productX < MOD) {
if (it->index <= pos && pos < prevIndex) {
// it->maxRangeY = segTreeRangeMax(it->index, prevIndex - 1);
int index = it->index;
relevantXs.erase(it);
relevantXs.insert(Index{index,
segTreeRangeMax(index, prevIndex - 1)});
break;
}
productX *= X[it->index];
prevIndex = it->index;
it--;
}
//dump();
return query();
}
