gcd

#include <iostream>
#include <vector>
using namespace std;
constexpr int len = 320;

int gcd(int a, int b) {
    while (a != 0 && b != 0) {
        if (a < b) {
            swap(a, b);
        }
        a = a % b;
    }
    return max(a, b);
}

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    vector<int> block_gcd(n / len + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> vec[i];
        block_gcd[i / len] = gcd(vec[i], block_gcd[i / len]);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r, --l, --r;
        int start = l / len;
        int finish = r / len;
        int cur_gcd = 0;
        if (l % len != 0){
            ++start;
        }
        if ((r + 1) % len != 0) {
            --finish;
        }
        for (int j = start; j <= finish; ++j) {
            cur_gcd = gcd(cur_gcd, block_gcd[j]);
        }
        for (int i = l; i < min(r + 1, start * len); ++i) {
            cur_gcd = gcd(cur_gcd, vec[i]);
        }
        for (int i = max(l, (finish + 1) * len); i <= r; ++i) {
            cur_gcd = gcd(cur_gcd, vec[i]);
        }
        cout << cur_gcd << " ";
    }
    return 0;
}