#include using namespace std; using ll=long long; using pll=pair; using tll=tuple; using ld=long double; const ll INF=(1ll<<60); #define rep(i,n) for (ll i=0;i<(ll)(n);i++) #define all(v) v.begin(),v.end() template inline bool chmin(T &a,T b){ if(a>b){ a=b; return true; } return false; } template inline bool chmax(T &a,T b){ if(a a,ll n,ll k){ //O(n) if(k==0) return 0; vector vr(n,0); ll r=0,sz=0; rep(l,n){ auto g=[&](ll idx){ ll p=0; if(cnt[a[idx]]==0) p=1; return (sz+p)<=k; }; while(r dp(n+1,0),sum(n+2,0); dp[0]=1; rep(i,n+1){ dp[i]+=sum[i]; if(INF a,ll s,auto &f){ //O(N) ll n=(ll)a.size(); ll ok=0; rep(i,n+1){ if(f(a,n,i)<=s) chmax(ok,i); else break; } cout << ok << '\n'; } void solve_b(vector a,ll s){ //O(M^2) return solve_linear(a,s,f_linear); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector x(n); rep(i,n) cin >> x[i]; x.push_back(INF); vector li,ri; ll cnt=1; rep(i,n){ if(x[i]==x[i+1]) cnt++; else{ if(cnt!=1){ li.push_back(i-cnt+1); ri.push_back(i+1); } cnt=1; } } ll q; cin >> q; while(q--){ ll l,r,s; cin >> l >> r >> s; l--; ll sz=r-l; if((1ll< a; for(ll i=l;i