#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL INF = (LL)1e9 + 7;
const LL NS = (LL)2e5 + 4;
LL lsum[NS], rsum[NS];
vector <int> ans;
vector <pair<LL, LL>>srt;
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
for(LL i = 0; i < (LL)w.size(); ++i){
srt.push_back(make_pair(w[i], i));
}
LL N = (LL)srt.size();
sort(srt.begin(), srt.end());
for(LL i = 0; i < N; ++i){
lsum[i] = srt[i].first;
if(i){
lsum[i] += lsum[i - 1];
}
}
for(LL i = N - 1; i >= 0; --i){
rsum[i] = srt[i].first + rsum[i + 1];
}
LL choose = -1;
for(LL i = 0; i < N; ++i){
LL low = lsum[i], high = rsum[N - i - 1];
if(low > high){
swap(low, high);
}
if(!(low > u || high < l)){
choose = i + 1;
}
}
if(choose == -1){
vector < int > emp;
return emp;
}
LL sum = 0;
ans.resize(choose);
for(LL i = N - 1; i >= N - choose; --i){
sum += srt[i].first;
ans[choose - (N - i)] = i;
}
int nxt = 0;
for(int i = 0; i < N; ++i){
if(i >= N - (choose - nxt) || nxt >= choose){
break;
}
if(sum - srt[ans[nxt]].first + srt[i].first < l){
continue;
}
sum += srt[i].first - srt[ans[nxt]].first;
ans[nxt] = i;
++nxt;
}
for(LL i = 0; i < choose; ++i){
ans[i] = srt[ans[i]].second;
}
sort(ans.begin(), ans.end());
return ans;
}
