While I'm doing problems on CSES like always, I met with a rather interesting problem : CSES-Stick Lengths. After solving it, I discover there was actually atleast 3 ways to do this problem (all in O(NlogN)): the one I used to AC, other one using Ternary Search, and finally, using a prominent solution that I saw others used. The idea for the third was short : You sort the whole array, take the middle (N/2) as the target value and calculate the result using it. Here it how it goes on USACO :

#include <bits/stdc++.h>

using namespace std;

//variables used for the current problem
int n,median;
vector<int> p;
long long ans,cnt;

void solve() {
	cin >> n;
	p.resize(n);
	for (int &x : p){
		cin >> x;
	}
	sort(p.begin(),p.end());
	median=p[n/2];
	for (const int &x : p){
		ans+=abs(median-x); //Calculate the cost to modify the stick length
	}
	cout << ans << "\n";
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

After a while of observation, I myself must admit the solution's correctness. But I just couldn't proof it. Can you guys help me with it ?