#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2000005;
int N,Q;
ll S[MAXN];
int ng[MAXN];
int st[MAXN],top;
int Lq[MAXN],Rq[MAXN],Tq[MAXN],idq[MAXN];
ll diffA[MAXN],valA[MAXN],prefA[MAXN],ans[MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
if(!(cin>>N)) return 0;
for(int i=1;i<=N;i++) cin>>S[i];
top=0;
for(int i=N;i>=1;i--){
while(top>0 && S[st[top-1]]<=S[i]) top--;
if(top==0) ng[i]=N+1; else ng[i]=st[top-1];
st[top++]=i;
}
cin>>Q;
for(int i=0;i<Q;i++){
cin>>Lq[i]>>Rq[i]>>Tq[i];
idq[i]=i;
}
unordered_map<int, vector<int>> mp;
mp.reserve(Q*2+10);
for(int i=0;i<Q;i++) mp[Tq[i]].push_back(i);
for(auto &pr: mp){
int T = pr.first;
if(T> N) T = N;
int t = T;
for(int i=1;i<=N+1;i++) diffA[i]=0;
for(int j=1;j<=N;j++){
int r = j + t;
if(r > N) r = N;
int ngpos = ng[j]-1;
if(ngpos < r) r = ngpos;
if(r >= j){
diffA[j] += S[j];
diffA[r+1] -= S[j];
}
}
ll cur=0;
for(int i=1;i<=N;i++){
cur += diffA[i];
valA[i]=cur;
prefA[i]=prefA[i-1]+valA[i];
}
for(int idx: pr.second){
int L=Lq[idx], R=Rq[idx];
ans[idq[idx]] = prefA[R] - prefA[L-1];
}
for(int i=0;i<=N;i++) prefA[i]=0;
}
for(int i=0;i<Q;i++) cout<<ans[i]<<"\n";
return 0;
}
