#include <bits/stdc++.h>
#define ll long long
#pragma GCC target("popcnt")
using namespace std;
int N;
vector <int> solve(vector <int> A)
{
  N = A.size();
  vector <pair <int, int>> V;
  for(int i = 0; i < N; i++) V.push_back({A[i], i});
  sort(V.begin(), V.end());
  vector <int> L, R, S;
  int cnt = 0, prev = 0;
  for(int i = 0; i < N; i++)
  {
    if(V[i].first == prev)
    {
      cnt++;
      if(cnt & 1)
      {
        if(i == (N - 1)) S.push_back(V[i].second);
        else if(V[i].first ^ V[i + 1].first) S.push_back(V[i].second);
        else L.push_back(V[i].second);
      }
      else R.push_back(V[i].second);
    }
    else
    {
      cnt = 1;
      if(i == (N - 1)) S.push_back(V[i].second);
      else if(V[i].first ^ V[i + 1].first) S.push_back(V[i].second);
      else L.push_back(V[i].second);
    }
  }
  if(S.size())
  {
    ll sum = 0, half;
    for(int x : S) sum += A[x];
    half = (sum + 1) >> 1;
    int mx = A[V.back().second];
    if(mx < half) exit(333);
    int n = S.size();
    for(int i = 0; i < ((n - 1) >> 1); i++) L.push_back(S[i]);
    L.push_back(S[n - 1]);
    for(int i = ((n - 1) >> 1); i < (n - 1); i++) R.push_back(S[i]);
  }
  for(int x : R) L.push_back(x);
  return L;
}