#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
template <typename t_it, typename comparator>
class heap_sorting{
public:
heap_sorting (const t_it& l, const t_it& r, const comparator& in) : cmp(in) , t(l-1), n(r-l) {
for (size_t i=n>>1; i; --i){
t_type temp=*(t+i);
sift_down(i,temp);
}
while (--n){
t_type temp=*(l+n);
*(l+n)=*l;
sift_down(1,temp);
}
}
private:
using t_type=iterator_traits<t_it>::value_type;
const t_it& t;
const comparator& cmp;
size_t n;
inline void sift_down (const size_t& root, const t_type& temp) {
size_t pos=root,c=pos<<1;
while (c<n){
c+=cmp(*(t+c),*(t+c+1));
if (cmp(temp,*(t+c))){
*(t+pos)=*(t+c);
pos=c;
c<<=1;
}
else
break;
}
if (c==n && cmp(temp,*(t+c))){
*(t+pos)=*(t+c);
pos=c;
}
*(t+pos)=temp;
}
};
template <typename t_it>
void heap_sort (const t_it& l, const t_it& r) {
heap_sorting instance(l,r,less<typename iterator_traits<t_it>::value_type>());
}
template <typename t_it, typename comparator>
void heap_sort (const t_it& l, const t_it& r, const comparator& cmp) {
heap_sorting instance(l,r,cmp);
}
bool cmp (const pair<int,int>& a, const pair<int,int>& b){
return a.first<b.first;
}
void energy(int n, vector<int> v){
vector<pair<int,int>> v2(n);
for (size_t i=0; i<n; i++)
v2[i]={v[i],i};
heap_sort(v2.begin(),v2.end(),cmp);
n>>=1;
for (size_t i=0; i<n; i++)
rotate({v2[i+n].second},v2[i].first+25000-v2[i+n].first);
}
