class Solution{
public:
    vector<int> segment_tree, v;
    int gcd(int a, int b) {
        if(a < b) {
            swap(a, b);
        }
        while(b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
    void build(int L, int R, int pos) {
        if(L == R) {
            segment_tree[pos] = v[L];
        }
        else {
            int mid = (L + R) / 2;
            build(L, mid, 2 * pos);
            build(mid + 1, R, 2 * pos + 1);
            segment_tree[pos] = gcd(segment_tree[2 * pos], segment_tree[2 * pos + 1]);
        }
    }
    int query(int L, int R, int pos, int i, int j) {
        // L R i L R  j L R
        if(i <= L and R <= j) {
            return segment_tree[pos];
        }
        if(R < i or j < L) {
            return 0;
        }
        int mid = (L + R) / 2;
        return gcd(query(L, mid, 2 * pos, i, j), query(mid + 1, R, 2 * pos + 1, i, j));
    }
    int findSmallestSubArr(int arr[], int n, int g) {
        int ok = -1;
        v.resize(n);
        for(int i = 0; i < n; i++) {
            if(arr[i] == g) {
                return 1;
            }
            if(arr[i] % g == 0) {
                ok = 1;
            }
            v[i] = arr[i];
        }
        if(ok == -1) {
            return -1;
        }
        segment_tree.resize(4 * n);
        build(0, n - 1, 1);
        int res = 2e9;
        for(int i = 0; i < n; i++) {
            if(v[i] % g == 0) {
                int L = i + 1, R = n - 1;
                int idx = -1;
                while(L <= R) {
                    int mid = L + (R - L) / 2;
                    int gcd = query(0, n - 1, 1, i, mid);
                    if(gcd == g) {
                        R = mid - 1;
                        idx = mid;
                    }
                    else if(gcd > g) {
                        L = mid + 1;
                    }
                    else {
                        R = mid - 1;
                    }
                }
                if(idx != -1) {
                    res = min(res, idx - i + 1);
                }
            }
        }
        if(res == 2e9) {
            res = -1;
        }
        return res;
    }
};