int maxScore(vector<int>& nums, int maxVal) {
        int n=nums.size();
        int max_elem=maxVal;
        for (int num:nums) {
            max_elem=max(max_elem,num);
        }
        vector<int>spf(max_elem+1);
        for (int i=2;i<=max_elem;i++)spf[i]=i;
        for (int i=2;i*i<=max_elem;i++) {
            if (spf[i]==i){
                for (int j=i*i;j<=max_elem; j += i) {
                    if (spf[j]==j)spf[j]=i;
                }
            }
        }
        vector<int>count_multiples(max_elem+1,0);
        vector<bool>in_nums(max_elem+1,false);
        for (int num:nums) {
            in_nums[num]=true;
            if (num==1)continue;
            vector<int> factors;
            int temp=num;
            while (temp>1) {
                int p=spf[temp];
                factors.push_back(p);
                while(temp%p==0)temp/= p;
            }
            int sz=factors.size();
            for (int mask=1;mask<(1<<sz);mask++) {
                int prod=1;
                for (int i=0;i<sz;i++) {
                    if ((mask>>i)&1) {
                        prod*=factors[i];
                    }
                }
                count_multiples[prod]++;
            }
        }


        auto get_not_coprime_count=[&](int x) {
            if (x==1)return 0;
            vector<int>factors;
            int temp=x;
            while (temp>1) {
                int p = spf[temp];
                factors.push_back(p);
                while (temp % p == 0) temp /= p;
            }

            int sz = factors.size();
            int res = 0;
            for (int mask = 1; mask < (1 << sz); mask++) {
                int prod = 1;
                int bits = 0;
                for (int i = 0; i < sz; i++) {
                    if ((mask >> i) & 1) {
                        prod *= factors[i];
                        bits++;
                    }
                }
                if (bits%2==1) res+=count_multiples[prod];
                else res-=count_multiples[prod];
            }
            return res;
        };
        vector<int> pos_x;
        for (int i = 1;i<=maxVal;i++) {
            pos_x.push_back(i);
        }
        for (int num:nums) {
            if (num>maxVal) {
                pos_x.push_back(num);
            }
        }
        sort(pos_x.begin(), pos_x.end());
        pos_x.erase(unique(pos_x.begin(), pos_x.end()),pos_x.end());
        int max_score = INT_MIN;
        for (int x : pos_x) {
            if (x == 1) {
                int cost=in_nums[1]?0:1;
                max_score=max(max_score,x-cost);
                continue;
            }

            int C = get_not_coprime_count(x);
            int cost = 0;
            if (in_nums[x]) {
                cost = C - 1;
            } else {
                cost=(C==0)?1:C;
            }
            max_score = max(max_score, x - cost);
        }

        return max_score;
    }