Suppose there are \(K\) points where at least one person (except for Takahashi) is standing, namely at points \(B_1, B_2,\ldots, B_K\) in ascending order, with \(P_1,P_2,\ldots,P_K\) persons, respectively.
His final position and score solely depend on between whom he starts, that is, which of the \(K\) intervals partitioned by the points with one or more persons he starts from. Specifically, for \(1\leq i\leq K-1\), we have \(X_{B_i}=X_{B_i+1}=\cdots X_{B_{i+1}-1}\) and \(X_{B_K}=X_{B_K+1}=\cdots=X_{M-1}=X_0=X_1=\cdots=X_{B_1-1}\). Denote these values as \(Y_1=X_{B_K}=X_{B_K+1}=\cdots=X_{M-1}=X_0=X_1=\cdots=X_{B_1-1}\), \(Y_{i+1}=X_{B_i}=X_{B_i+1}=\cdots X_{B_{i+1}-1}\) \((1\leq i\leq K-1)\).

We will consider how to find \(Y_i\) \((1\leq i\leq K)\). Define \(P_{K+1},P_{K+2},\ldots,P_{2K}\) by \(P_{K+i}=P_i\) \((1\leq i\leq K)\).
Also, let \(R_i\) be the integer with \(P_i+P_{i+1}+\cdots+P_{R_i-1}< C\) and \(P_i+P_{i+1}+\cdots+P_{R_i}\geq C\). Then \(Y_i=P_i+P_{i+1}+\cdots+P_{R_i}\). Note that since \(P_i+P_{i+1}+\cdots+P_{K+i-1}=N\geq C\), it holds that \(R_i\leq K+i-1\).
By definition, \(R_i\) satisfy \( R_1\leq R_2\leq\cdots\leq R_K\).
Thus, \(R_1,R_2,\ldots,R_K\) can be found by the sliding window trick.
Specifically, follow these steps:

1. Find \(R_1\) naively. That is, iterate \(j=1,2,3,\ldots\) to find the minimum \(j\) such that \(P_1+P_2+\cdots+P_j\geq C\).
2. Suppose we already know \(R_i\). Starting from \(j=R_i\), iterate \(j=R_i,R_{i}+1,\ldots,\) to find the minimum \(j\) (\(=R_{i+1}\)) such that \(P_{i+1}+P_{i+2}+\cdots+P_j\geq C\). Here, note that the sum for the initial \(j\), namely the value \(P_{i+1}+P_{i+2}+\cdots+P_{R_i}\), can be computed as \((P_{i}+P_{i+2}+\cdots+P_{R_i})-P_i\).

Once we find these values, the answer can be computed as \((B_2-B_1)\times Y_2+(B_3-B_2)\times Y_3+\cdots +(B_K-B_{K-1})\times Y_K+(M+B_1-B_K)\times Y_1\).

Here, since \(R_K\leq 2K-1\) and \(K\leq N\), the sum computation costs at most \(O(N)\) time.
Also, by considering the delta from the previous result, the sum can be updated in \(O(1)\) time each. The values \((B_1, B_2,\ldots, B_K)\) and \((P_1, P_2,\ldots, P_K)\) can be computed with sorting or map in \(O(N\log N)\), and then the answer can be found in \(O(N)\) time, which is fast enough.

Sample code in C++:

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

#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	int n;
	long long m,c;
	cin>>n>>m>>c;
	vector<long long>a(n);
	rep(i,n)cin>>a[i];
	sort(a.begin(),a.end());

	vector<long long>b;
	vector<int>p;
	int idx=0,nxt;
	while(idx<n){
		b.push_back(a[idx]);
		nxt=idx+1;
		while(nxt<n){
			if(a[nxt]!=a[idx])break;
			nxt++;
		}
		p.push_back(nxt-idx);
		idx=nxt;
	}

	int k=b.size();
	int r=0;
	long long cur=0, ans=0;
	rep(i,k){
		while(cur<c){
			cur+=p[r];
			r++;
			if(r>=k)r-=k;
		}
		if(i==0)ans+=(m+b[0]-b[k-1])*cur;
		else ans+=(b[i]-b[i-1])*cur;
		cur-=p[i];
	}
	cout<<ans<<endl;

	return 0;
}