#include #define endl '\n' using namespace std; using ll=long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector x(n); for(int i=0;i>x[i]; vector sum(n); for(int i=0;i>q; while(q--){ ll l,r,s; cin>>l>>r>>s; --l; --r; if(sum[r]-sum[l]>60||(1ll<<(sum[r]-sum[l]))>s){ cout<<0<=100){ cout<<1<1){ int m=(ok+ng)/2; vector mp(n+1); int j=l,cnt=0; vector dp(r-l+3); bool isok=false; dp[0]=1; dp[1]=-1; for(int i=l;i<=r;i++){ while(j<=r&&cnt<=m){ if(mp[x[j]]==0) cnt++; if(cnt>m){ cnt--; break; } mp[x[j]]++; j++; } if(dp[i-l]>s){ isok=true; break; } dp[i-l+1]+=dp[i-l]*2; dp[j-l+1]-=dp[i-l]; mp[x[i]]--; if(mp[x[i]]==0) cnt--; } if(isok||dp[r-l+1]>s) ng=m; else ok=m; } cout<