// LUOGU_RID: 167584202
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,f[N][105],k,mod,a[N],tq[105],th[105];
inline void clear(){
	for(int i=1;i<=mod;++i)tq[i]=th[i]=2e9;
}
inline void insert(int pos,int x){
	int zc=pos;
	for(;pos<=mod;pos+=pos&-pos)tq[pos]=std::min(tq[pos],x);
	pos=mod-zc+1;
	for(;pos<=mod;pos+=pos&-pos)th[pos]=std::min(th[pos],x);
}
inline int query(int pos){
	int res=2e9;
	for(int i=pos;i;i-=i&-i)res=std::min(res,tq[i]);
	pos++;pos=mod-pos+1;
	for(int i=pos;i;i-=i&-i)res=std::min(res,th[i]+mod);
	return res;
}

signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	double cl=clock();
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),k=read(),mod=read();
	clear();
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)a[i]=(read()+a[i-1])%mod;
    for(int j=1;j<=k;++j){
    	clear();
    	if(j==1)insert(1,0);
    	for(int i=std::max(j-1,1ll);i<=n;++i){
    		f[i][j]=query(a[i]+1)+a[i];
    		insert(a[i]+1,f[i][j-1]-a[i]);
    	}
    }
	std::cout<<f[n][k]<<'\n';
	std::cerr<<(clock()-cl)/1000<<'\n';
}

树状数组 $\mathcal{O}(nk\log p)$ 写法，极限数据 CF 上 T 了，但是本地很稳，甚至样例也比 CF 快很多。
求教教。