#include <iostream>
#include <string>
#include <vector>
#include "partition.h"
#include <algorithm>
using namespace std ;
vector<int> solve(std::vector<int> a){
    long long n = a.size();
    vector<int> sol;
    int ma=a[0];
    int index=0;
    for (int i=0;i<n;i++){
        sol.push_back(i);
        if (ma<a[i]){
            ma=a[i];
            index=i;
        }

    }
    long long tem=sol[(n-1)/2];
    sol[(n-1)/2]=sol[index];
    sol[index]=tem;
    return sol;
    /*
    vector<pair<int,int>> b;
    long long sumt=0;
    for (long long i=0; i<n;i++){
        b.push_back({a[i],i});
        sumt+=a[i];

    }
    sort(b.begin(),b.end());
    if ( n==2){
        return {b[1].second,b[0].second};
    }
    if (n>=10e5+5){
        return {0,0};
    }
    long long sum=0;
    long long i=0;
    long long mid =n/2;
    float midf =n/2 ;
    if (n%2==1){
        midf+=0.5;
    }
    long long midi= (n+1)/2-1;
    while (i*2<n){
       
        sum+= b[i].first;
        i++;

    }
    long long j=0;
    while (sum*2 <=sumt ){
        sum-=b[j].first;
        sum +=b[n-j-1].first;
        j++;

    }
    
    vector<int> finale(n);
    
    for (long long k=0; k<midf;k++){
        if (k<j){
            finale[mid+k]=b[k].second;
        }
        else{
            finale[k-j]=b[k].second;
        }
    }
    
    for (long long k=n;n-k<j;k--){
        finale[k-mid-1]=b[k-1].second;
    }
    for (long long k=n-j-1;k>midi;k--){
        finale[k+j]=b[k].second;
    }
    return finale;
    */

}