#include "horses.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
typedef long double ld;
int add (int a, int b) {
a += b; if (a >= MOD) a -= MOD;
return a;
}
int sub (int a, int b) {
a -= b; if (a < 0) a += MOD;
return a;
}
int mul (int a, int b) {
return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
if (!b) return 1;
int u = power(a, b >> 1);
u = mul(u, u);
if (b & 1) u = mul(u, a);
return u;
}
int inv (int x) {
return power(x, MOD - 2);
}
int x[MAXN], y[MAXN], n;
struct SegmentTree {
pair <ld, int> tree[MAXN << 2];
ld lazy[MAXN << 2];
void init (int l, int r, int node) {
lazy[node] = 0; tree[node] = {ld(0), l};
if (l == r) {
return;
}
init(l, mid, tl); init(mid + 1, r, tr);
}
void prop (int l, int r, int node) {
if (lazy[node] == 0) return;
if (l != r) {
lazy[tl] += lazy[node];
lazy[tr] += lazy[node];
}
tree[node].first += lazy[node];
lazy[node] = 0;
}
void update (int l, int r, int a, int b, ld c, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] += c;
prop(l, r, node);
return;
}
update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
tree[node] = max(tree[tl], tree[tr]);
}
} cur;
struct SegmentTree2 {
int tree[MAXN << 2], lazy[MAXN << 2];
void init (int l, int r, int node) {
tree[node] = 1; lazy[node] = 1;
if (l == r) return;
init(l, mid, tl); init(mid + 1, r, tr);
}
void prop (int l, int r, int node) {
if (l != r) {
lazy[tl] = mul(lazy[tl], lazy[node]);
lazy[tr] = mul(lazy[tr], lazy[node]);
}
tree[node] = mul(tree[node], lazy[node]);
lazy[node] = 1;
}
void update (int l, int r, int a, int b, int c, int node) {
prop(l, r, node);
if (l > b || r < a) return;
if (l >= a && r <= b) {
lazy[node] = mul(lazy[node], c);
prop(l, r, node);
return;
}
update(l, mid ,a, b, c, tl);
update(mid + 1, r, a, b, c, tr);
}
int get (int l, int r, int a, int node) {
prop(l, r, node);
if (l == r) return tree[node];
if (a <= mid) return get(l, mid, a, tl);
else return get(mid + 1, r, a, tr);
}
} cur2;
int ans () {
auto z = cur.tree[1];
return cur2.get(0, n - 1, z.second, 1);
}
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];
}
cur.init(0, n - 1, 1);
cur2.init(0, n - 1, 1);
for (int i = 0; i < n; i++) {
cur.update(0, n - 1, i, n - 1, log2(x[i]), 1);
cur2.update(0, n - 1, i, n - 1, x[i], 1);
cur.update(0, n - 1, i, i, log2(y[i]), 1);
cur2.update(0, n - 1, i, i, y[i], 1);
}
return ans();
}
int updateX (int pos, int val) {
cur.update(0, n - 1, pos, n - 1, log2(val) - log2(x[pos]), 1);
cur2.update(0, n - 1, pos, n - 1, mul(val, inv(x[pos])), 1);
x[pos] = val;
return ans();
}
int updateY (int pos, int val) {
cur.update(0, n - 1, pos, pos, log2(val) - log2(y[pos]), 1);
cur2.update(0, n - 1, pos, pos, mul(val, inv(y[pos])), 1);
y[pos] = val;
return ans();
}
