TOI16: Dino Cell

#include <bits/stdc++.h>
using namespace std;

const int K = 1e7 + 5;

int qs[K], k;

int getSum(int i){
    return qs[k] * (i / k) + qs[i % k];
}

int main(){

    int n;
    scanf("%*d%d%d", &k, &n);
    for(int i = 2; i <= k; ++i){
        if(k % i == 0 && qs[i] == 0){
            for(int j = i; j <= k; j += i){
                qs[j] = 1;
            }
        }
    }
    for(int i = 1; i <= k; ++i){
        if(qs[i] == 0){
            qs[i] = -1;
        }
        qs[i] += qs[i - 1];
    }

    int pmn = 2e9;
    int pmx = -2e9;
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int x;
        scanf("%d", &x);
        int sum = getSum(x);
        int prv = getSum(x - 1);
        int mx = i == 1 ? sum : sum + pmx;
        int mn = i == 1 ? sum : sum + pmn;
        ans = max(ans, max(mx, -mn));
        pmx = max(pmx, -prv);
        pmn = min(pmn, -prv);
    }
    cout << ans;

    return 0;
}