Horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

typedef long long llint;
typedef set <int> :: iterator iter;

const int MAXN = 500005;
const int INF = 1000000000;
const int MOD = 1000000007;

int n, ofs = 1;
llint x[MAXN], y[MAXN];
int t[4*MAXN];
set <int> st;
vector < pair <int, int> > v;
llint fen[MAXN];

void ubaci (int xx, llint val) {
    xx++;
    for (; xx < MAXN; xx += xx&-xx) {
        fen[xx] = (fen[xx] * val) % MOD;
    }
}

llint get (int ind) {
    llint res = 1;
    ind++;
    for (; ind > 0; ind -= ind&-ind) res = (res * fen[ind]) % MOD;
    return res;
}

void build () {
    while (ofs < n) ofs *= 2;
    for (int i=0; i<n; i++) {
        t[i + ofs] = y[i];
    }
    for (int i = ofs-1; i>0; i--) {
        t[i] = max(t[2*i], t[2*i+1]);
    }
}

int upit (int xx, int from, int to, int low, int high) {
    if (from <= low && high <= to) return t[xx];
    if (to < low || high < from) return 0;
    return max(upit(xx*2, from, to, low, (low + high)/2), upit(xx*2+1, from, to, (low + high)/2 + 1, high));
}

void update (int pos, int val) {
    pos += ofs;
    t[pos] = val;
    pos /= 2;
    while (pos > 0) {
        t[pos] = max(t[pos*2], t[pos*2+1]);
        pos /= 2;
    }
}

llint calc () {
    __int128 mx = 0, curr = 1, pos = 0, mxy = 1;
    for (int i=(int)v.size()-1; i>=0; i--) {
        int ind = v[i].first, yi = v[i].second;
        curr *= x[ind];
        if (curr * yi > mx) {
            mx = curr * yi;
            mxy = yi;
            pos = ind;
        }
    }
    return get(pos) * mxy % MOD;
}

llint rjesi () {
    v.clear();
    if (st.empty()) {
        v.push_back(make_pair(0, t[1]));
    } else {
        llint p = 1;
        iter it = st.end(); it--;
        int prosli = n;
        while (1) {
            int ind = *it;
            p *= x[ind];
            v.push_back(make_pair(ind, upit(1, ind, prosli-1, 0, ofs-1)));
            prosli = ind;
            if (p > INF || it == st.begin()) break;
            it--;
        }
        if (p <= INF && prosli != 0) {
            v.push_back(make_pair(0, upit(1, 0, prosli-1, 0, ofs-1)));
        }
    }
    return calc();
}

int init (int N, int X[], int Y[]) {
    n = N;
    for (int i=0; i<MAXN; i++) {
        fen[i] = 1;
    }
    for (int i=0; i<n; i++) {
        x[i] = X[i]; y[i] = Y[i];
        if (x[i] != 1) st.insert(i);
        ubaci(i, x[i]);
    }
    build();
    return rjesi();
}

llint pot (llint b, llint e) {
    if (e == 0) return 1;
    if (e & 1) {
        return pot(b, e-1) * b % MOD;
    } else {
        llint t = pot(b, e / 2);
        return t * t % MOD;
    }
}

int updateX(int pos, int val) {
    llint inv = pot(x[pos], MOD-2);
    ubaci(pos, inv);
    if (x[pos] != 1) st.erase(pos);
    x[pos] = val;
    ubaci(pos, val);
    if (x[pos] != 1) st.insert(pos);
    return rjesi();
}

int updateY(int pos, int val) {
    update(pos, val);
    return rjesi();
}