（高橋くんを除いて）\(1\) 人以上の人が立っている場所の数を \(K\) とし、その地点を昇順に \(B_1, B_2,\ldots, B_K\) 、それぞれの地点にいる人数を順に \(P_1,P_2,\ldots,P_K\) とします。
高橋君が止まる位置およびスコアは、高橋君が誰の間からスタートするか、すなわち人が立っている地点によって区切られた \(K\) 個の区間のどれからスタートしたかにしか依存しません。具体的には、各 \(1\leq i\leq K-1\) について \(X_{B_i}=X_{B_i+1}=\cdots X_{B_{i+1}-1}\) および、 \(X_{B_K}=X_{B_K+1}=\cdots=X_{M-1}=X_0=X_1=\cdots=X_{B_1-1}\) が成り立ちます。 この値を \(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)\) とします。

\(Y_i\) \((1\leq i\leq K)\) を求めることを考えます。 また、以下では \(P_{K+1},P_{K+2},\ldots,P_{2K}\) について、\(P_{K+i}=P_i\) \((1\leq i\leq K)\) と定義します。
\(R_i\) を 、\(P_i+P_{i+1}+\cdots+P_{R_i-1}< C\) かつ \(P_i+P_{i+1}+\cdots+P_{R_i}\geq C\) をみたす整数と定義すると、\(Y_i=P_i+P_{i+1}+\cdots+P_{R_i}\) となります。なお、\(P_i+P_{i+1}+\cdots+P_{K+i-1}=N\geq C\) より、\(R_i\leq K+i-1\) が成り立ちます。
\(R_i\) について、 定義より\( R_1\leq R_2\leq\cdots\leq R_K\) が成り立ちます。
よって、\(R_1,R_2,\ldots,R_K\) を尺取り法の要領で求めることができます。
すなわち、以下の方法で求めることができます。

1. \(R_1\) は愚直に求める。すなわち、\(j=1,2,3,\ldots\)　の順で、\(P_1+P_2+\cdots+P_j\geq C\) となる最小の \(j\) を求める。
2. \(R_i\) が求まっている時、\(j=R_i\) から始めて、\(j=R_i,R_{i}+1,\ldots,\) の順で\(P_{i+1}+P_{i+2}+\cdots+P_j\geq C\) となる最小の \(j\) （ \(=R_{i+1}\)）を求める。なお、最初の \(j\) における総和、すなわち \(P_{i+1}+P_{i+2}+\cdots+P_{R_i}\)の値は \((P_{i}+P_{i+2}+\cdots+P_{R_i})-P_i\) として求められることに注意する。

このようにして求められた値を元に、答えは \((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\) として求めることができます。

このとき、\(R_K\leq 2K-1\), \(K\leq N\) より、総和の計算は高々 \(O(N)\) しか行われません。
また、直前の区間との差分をもとに計算することで、総和の計算はそれぞれ \(O(1)\) で行うことができます。最初の \((B_1, B_2,\ldots, B_K)\), \((P_1, P_2,\ldots, P_K)\) はソートや map によって、\(O(N\log N)\) で求められ、その後答えを \(O(N)\) で求めることができるため、十分高速です。

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;
}