#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct segtree{
int size;
vector<ll> values;
void build(vector<int> &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<(int)a.size()){
values[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
values[x]=min(values[2*x+1],values[2*x+2]);
}
void build(vector<int> &a){
build(a,0,0,size);
}
void init(int n){
size=1;
while(size<n){
size*=2;
}
values.assign(2*size,0LL);
}
ll calc(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l){
return INT_MAX;
}
if(lx>=l && rx<=r){
return values[x];
}
ll s1,s2;
int m=(lx+rx)/2;
s1=calc(l,r,2*x+1,lx,m);
s2=calc(l,r,2*x+2,m,rx);
return min(s1,s2);
}
ll calc(int l,int r){
return calc(l,r,0,0,size);
}
};
struct segtree1{
int size;
vector<ll> values;
void build(vector<int> &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<(int)a.size()){
values[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
values[x]=max(values[2*x+1],values[2*x+2]);
}
void build(vector<int> &a){
build(a,0,0,size);
}
void init(int n){
size=1;
while(size<n){
size*=2;
}
values.assign(2*size,INT_MIN);
}
ll calc(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l){
return INT_MIN;
}
if(lx>=l && rx<=r){
return values[x];
}
ll s1,s2;
int m=(lx+rx)/2;
s1=calc(l,r,2*x+1,lx,m);
s2=calc(l,r,2*x+2,m,rx);
return max(s1,s2);
}
ll calc(int l,int r){
return calc(l,r,0,0,size);
}
};
vector<int> find_subset(int l, int u, std::vector<int> w) {
vector<int> ans;
ll n=w.size();
ll a[n+5];
segtree st;
segtree1 st1;
st.init(n);
st1.init(n);
vector<int> b(n,0);
for(int i=0;i<n;i++)
{
b[i+1]=b[i]+w[i];
}
st.build(b);
st1.build(b);
ll le=1,r=n;
while(le<r)
{
if(b[r]-b[le-1]>=l && b[r]-b[le-1]<=u )
{
le--;
r--;
for(int i =le;i<=r;i++)
{
ans.push_back(i);
}
return ans;
}
else if(b[r]-b[le-1]>u)
{
le++;
}
else
{
r--;
}
}
return ans;
}
