#include "horses.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
using namespace std;
const long long MOD = 1e9 +7;
int N;
int X[500005], Y[500005];
int treeX[2000000];
long long sumX[2000000];
int mxY[2000000];
int last, now;//product sum suffix skrg
int pointer;//posisi suffix skrg
int residue;//product sum % MOD prefix skrg
//segtree 2 buah dan 1 BIT nice
int kali(long long a, long long b) {
return a * b > 1000000000 ? 1000000001 : a * b;
}
//segtreeX
void buildX(int n, int l, int r) {
if(l == r) {
treeX[n] = X[l];
sumX[n] = X[l];
// cout << X[l] << " ";
return;
}
int mid = (l + r) >> 1;
buildX(L(n), l, mid);
buildX(R(n), mid + 1, r);
treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}
void upX(int n, int l, int r, int pos, int val) {
if(l == r) {
treeX[n] = val;
sumX[n] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) upX(L(n), l, mid, pos, val);
else upX(R(n), mid + 1, r, pos, val);
treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}
//query mencari suffix terpanjang yang product sumnya < sum suffix sekarang
void findposX(int n, int l, int r, long long need = last) {
// cout << l << " " << r << " " << need << "\n";
// cout << treeX[L(n)] << " " << treeX[R(n)] << "\n";
if(l == r) {
pointer = l;
return;
}
int mid = (l + r) >> 1;
if(treeX[R(n)] >= need) findposX(R(n), mid + 1, r, need);
else {
now *= treeX[R(n)];
need = ceil((double) need / treeX[R(n)]);
findposX(L(n), l, mid, need);
}
}
long long sum_query_modX(int n, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return sumX[n];
}
int mid = (l + r) >> 1;
long long res = 1;
if(ql <= mid) res *= sum_query_modX(L(n), l, mid, ql, qr);
if(qr > mid) res *= sum_query_modX(R(n), mid + 1, r, ql, qr);
return res % MOD;
}
int sum_queryX(int n, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return treeX[n];
}
int mid = (l + r) >> 1;
int res = 1;
if(ql <= mid) res = kali(res, sum_queryX(L(n), l, mid, ql, qr));
if(qr > mid) res = kali(res, sum_queryX(R(n), mid + 1, r, ql, qr));
return res;
}
void buildX() {buildX(1, 0, N);}//cout << "\n";}
void upX(int pos, int val) {upX(1, 0, N, pos, val);}
void findposX() {findposX(1, 0, N);}
long long sum_query_modX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_query_modX(1, 0, N, l, r) : 1;}
long long sum_queryX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_queryX(1, 0, N, l, r) : 1;}
//segtree X end
//segtree Y
void buildY(int n, int l, int r) {
if(l == r) {
mxY[n] = Y[l];
return;
}
int mid = (l + r) >> 1;
buildY(L(n), l, mid);
buildY(R(n), mid + 1, r);
mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}
void upY(int n, int l, int r, int pos, int val) {
if(l == r) {
mxY[n] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) upY(L(n), l, mid, pos, val);
else upY(R(n), mid + 1, r, pos, val);
mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}
int rmqY(int n, int l, int r, int pos) {
if(pos <= l) return mxY[n];
int mid = (l + r) >> 1;
int res = 0;
if(pos <= mid) res = rmqY(L(n), l, mid, pos);
res = max(res, rmqY(R(n), mid + 1, r, pos));
return res;
}
void buildY() {buildY(1, 1, N);}
void upY(int pos, int val) {upY(1, 1, N, pos, val);}
int rmqY(int pos) {
if(pos > N || pos < 1) return 0;
return rmqY(1, 1, N, pos);
}
//segtree Y end
int solve() {
long long res = 1;
long long bef = 1;
long long sisa = 1;
last = treeX[1];
// cout << "\n";
// buildX();
if(last != 1000000001) res = rmqY(1);
else {
int l = 0, r = N;
pointer = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(sum_queryX(mid, N) == 1000000001) {
l = mid + 1;
}else {
pointer = mid;
r = mid - 1;
}
}
// cout << sum_queryX(8, 10) << "\n";
// cout << sum_queryX(9, 10) << "\n";
res = rmqY(pointer + 1);
last = sum_queryX(pointer, N);
sisa = sum_query_modX(0, pointer - 1);
// cout << 0 << " " << pointer << ": " << sisa << " <=\n";
// cout << rmqY(pointer + 1) << "\n";
// cout << pointer << " - \n";
}
while(1) {
now = 1;
findposX();
bef *= last / now;
res = max(res, bef * rmqY(pointer + 1));
// cout << bef << " " << rmqY(pointer + 1) << " = " << bef * rmqY(pointer + 1) << "\n";
// cout << "sum sebelumnya: " << last << "\n";
// cout << "sum sekarang: " << now << "\n";
// cout << "posisi skrg: " << pointer << "\n";
// cout << "bef: " << bef << "\n";
// cout << "best di array Y di range "<< pointer + 1 << " " << N << " : " << rmqY(pointer + 1) << "\n\n";
if(now == 1 || pointer >= N) break;
swap(now, last);
}
return (res % MOD * sisa % MOD);
}
int init(int n, int x[], int y[]) {
N = n;
for(int i = 0; i < N; i++) X[i] = x[i], Y[i + 1] = y[i];
X[N] = 1;
buildX();
buildY();
return solve();
}
int updateX(int pos, int val) {
X[pos] = val;
upX(pos, val);
return solve();
}
int updateY(int pos, int val) {
upY(pos + 1, val);
return solve();
}
