#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 struct fenwick_tree{ vector v; int n; fenwick_tree(int x){ n=x+1; v.assign(n+1,0); } fenwick_tree(vector &a){ n=(int)a.size()+1; v.assign(n+1,0); if((int)a.size()==0) return; v[1]=a[0]; for(int i=0;i>=1){ if(x+k<=n&&v[x+k] a,ll n,ll k){ //O(nlogn) if(k==0) return 0; vector vr(n,0); ll r=0,sz=0; unordered_map mp; rep(l,n){ auto g=[&](ll idx){ ll p=0; if(mp[a[idx]]==0) p=1; return (sz+p)<=k; }; while(r st(n+1,0); st[0]=1; fenwick_tree<__int128> BIT(st); rep(i,n){ 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); } cout << ok << '\n'; } void solve_binary(vector a,ll s,auto &f){ //O(logN) ll n=(ll)a.size(); ll ok=0,ng=n+1; while(1 a,ll s){ //O(M^2logM) return solve_linear(a,s,f_log); } 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