simple queries

const int N = 1e5+5;
#define vll vector<int>
#define ll long long
const ll M = 1e9+7;

struct segTree {
    int size = 1;
    vll maxs;

    segTree(int n) {
        while(size < n) size <<= 1;
        maxs.assign((size << 1), 0);
    }

    void _build(int n, vll& v, int x, int lx, int rx) {
        if(rx-lx == 1) {
            if(lx < n) maxs[x] = v[lx];
            return;
        }
        int m = (lx+rx)/2;
        _build(n, v, 2*x+1, lx, m);
        _build(n, v, 2*x+2, m, rx);
        maxs[x] = max(maxs[2*x+1], maxs[2*x+2]);
    }

    void build(int n, vll& v) {
        _build(n, v, 0, 0, size);
    }

    void _set(int i, ll v, int x, int lx, int rx) {
        if(rx-lx == 1) {
            maxs[x] = v;
            return;
        }
        int m = (lx+rx)/2;
        if(i < m) _set(i, v, 2*x+1, lx, m);
        else _set(i, v, 2*x+2, m, rx);
        maxs[x] = max(maxs[2*x+1], maxs[2*x+2]);
    }

    void set(int i, ll v) {
        _set(i, v, 0, 0, size);
    }

    ll _getMax(int l, int r, int x, int lx, int rx) {
        if(l >= rx || lx >= r) return 0;
        if(l <= lx && rx <= r) return maxs[x];
        int m = (lx+rx)/2;
        return max(_getMax(l, r, 2*x+1, lx, m), _getMax(l, r, 2*x+2, m, rx));
    }

    ll getMax(int l, int r) {
        return _getMax(l, r, 0, 0, size);
    }
};

int search(vector<pair<ll, ll>>& v, ll x) {
    int l = 0, r = v.size()-1; ll ans = -1;
    while(l <= r) {
        int m = l+(r-l)/2;
        if(v[m].second >= x) {
            r = m-1;
            ans = v[m].first;
        } else {
            l = m+1;
        }
    }
    return ans;
}

vector<int> Solution::solve(vector<int> &A, vector<int> &B) {
    int n = A.size();
    vector<long long> arr(N, 0);
    vector<long long> prev(N, 0);
    vector<long long> prod(N, 1);
    segTree st(n); st.build(n, A);
    for(int i = 0; i < n; i++) {
        int l = i+1, r = n;
        while(l <= r) {
            int m = l+(r-l)/2;
            if(st.getMax(i, m) == A[i]) l = m+1;
            else r = m-1;
        }
        int l1 = prev[A[i]], r1 = i;
        while(l1 <= r1) {
            int m = l1+(r1-l1)/2;
            if(st.getMax(m, i+1) == A[i]) r1 = m-1;
            else l1 = m+1;
        }
        arr[A[i]] += (long long)(r-i)*(long long)(i-l1+1);
        prev[A[i]] = (long long)(i+1);
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            prod[j] = (prod[j]*i)%M;
        }
    }
    map<ll, ll> m;
    for(int i = 1; i < N; i++) if(arr[i] > 0) m[prod[i]] += arr[i];
    vector<pair<ll, ll>> v(m.begin(), m.end());
    int p = v.size();
    reverse(v.begin(), v.end());
    for(int i = 1; i < p; i++) v[i].second += v[i-1].second;
    //for(int i = 0; i < p; i++) cout << "(" << v[i].first << "," << v[i].second << ") ";
    //cout << "\n";
    vector<int> ans;
    for(ll x : B) ans.push_back(search(v, x));
    return ans;
}