#include<bits/stdc++.h>
#include "molecules.h"
using namespace std;
bool construct(vector<int>& range, vector<pair<int,int> >& a, vector<int>& sol, int left, int right){
int n=a.size();
int x=0;
int i=0;
reverse(range.begin(), range.end()); //=> aufsteigend
range.push_back(INT_MAX);
reverse(a.begin(), a.end()); //=> aufsteigend
/*for(auto e: a){
cout << e.first << " " << e.second << "\n";
}
cout << "=====\n";
for(auto e: range){
cout << e << "\n";
}
cout << ":::::::::::::::::::::::::\n";*/
for(int j=0; j<n; j++){
if(range[j+1]<x) continue;
int l=range[j];
while(i<=j && x<l+(a[j].first-a[i].first)){
//cout << j << " " << i << "\n";
i++;
}
if(i>j) return false;
//cout << x << " " << range[j] << " " << a[i].first << "\n";
sol.push_back(a[i].second);
x+=a[i].first;
i++;
}
if(x<left || right<x) return false;
return true;
}
vector<int> find_subset(int l, int r, vector<int> a){
int n=a.size();
vector<pair<int,int> > b(n);
for(int i=0; i<n; i++){
b[i]={a[i], i};
}
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
vector<int> range(1, l);
for(int i=0; i<n; i++){
range.push_back(range[i]-b[i].first);
}
/*for(auto e: range){
cout << e.first << " " << e.second << "\n";
}*/
vector<int> sol;
if(construct(range, b, sol, l, r)){
return sol;
}
return {};
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n);
for(int i=0; i<n; i++){
cin >> a[i];
}
vector<int> sol=find_subset(l, r, a);
for(auto e: sol){
cout << e << " ";
}
cout << "\n";
}*/
