#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
long long n, lower, upper;
vector<pair<long long, long long> > store;
long long pf[200001];
void pfcompute() {
pf[0] = store[0].first;
for (long long i=1; i<n; i++) {
pf[i] = pf[i-1] + store[i].first;
}
}
long long pfquery(long long a, long long b) {
if (a == 0) return pf[b];
return pf[b] - pf[a-1];
}
pair<long long, long long> solve_for(long long left) {
//
long long low = left;
long long high = n;
long long mid;
while (low + 1 < high) {
mid = (low + high) / 2;
long long sumr = pfquery(left, mid);
if (sumr > upper) {
high = mid;
}
else if (sumr < lower) {
low = mid;
}
else {
return make_pair(left, mid);
}
}
if (pfquery(left, left) <= upper && pfquery(left, left) >= lower) {
return make_pair(left, left);
}
if (pfquery(left, low) <= upper && pfquery(left, low) >= lower) {
return make_pair(left, low);
}
if (high != n) {
if (pfquery(left, high) <= upper && pfquery(left, high) >= lower) {
return make_pair(left, high);
}
}
return make_pair(-1, -1);
}
vector<int> find_subset(int l, int u, vector<int> w) {
//
n = w.size();
lower = l;
upper = u;
for (long long i=0; i<n; i++) {
store.push_back(make_pair(w[i], i));
}
sort(store.begin(), store.end());
/*for (int i=0; i<n; i++) {
cout << store[i].first << ":" << store[i].second << endl;
}*/
pfcompute();
vector<int> ind;
for (long long leftlock=0; leftlock<n; leftlock++) {
pair<long long, long long> res = solve_for(leftlock);
if (res.first == -1 && res.second == -1) {
continue;
}
else {
for (long long i=res.first; i<=res.second; i++) {
ind.push_back(store[i].second);
}
return ind;
}
}
return ind;
}
