func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 3e5 + 5;   const int MAXQ = 3e5 + 5;   const int inf = 0x3f3f3f3f;   struct Query {     int id, l, r;     Query(void) {}     Query(int _id, int _l, int _r) : id(_id), l(_l), r(_r) {}   };   long long res[MAXQ];   struct Solver {     vector<int> a, b;     vector<Query> qs;     void solve(void) {       int n = (int)a.size();       a.push_back(-inf);       b.push_back(-inf);       vector<vector<Query> > f(n), g(n);       for (Query x : qs) x.r = min(x.r, n - 1), f[x.l].push_back(x);       vector<int> sta(1, n), val(1, -inf);       for (int i = n - 1; i >= 0; --i) {         int pos = lower_bound(val.begin(), val.end(), b[i]) - val.begin();         pos = sta[pos - 1];         for (Query x : f[i]) {           int id = x.id, l = x.l, r = x.r;           if (pos > r) {             res[id] = (long long)(r - l + 1) * b[i];             continue;           }           res[id] = (long long)(pos - l) * b[i];           x.l = pos;           g[pos].push_back(x);         }         while (val.back() >= a[i]) val.pop_back(), sta.pop_back();         sta.push_back(i);         val.push_back(a[i]);       }       sta = vector<int>(1, n);       val = vector<int>(1, -inf);       vector<long long> sum(1, 0);       for (int i = n - 1; i >= 0; --i) {         while (val.back() >= a[i]) {           val.pop_back();           sta.pop_back();           sum.pop_back();         }         sum.push_back((long long)a[i] * (sta.back() - i) + sum.back());         sta.push_back(i);         val.push_back(a[i]);         for (Query x : g[i]) {           int id = x.id, r = x.r;           int pos = lower_bound(sta.begin(), sta.end(), r, greater<int>()) -                     sta.begin();           res[id] += sum.back() - sum[pos];           res[id] += (long long)(x.r - sta[pos] + 1) * val[pos];         }       }     }   } slv[MAXN];   int a[MAXN], f[MAXN];   int main(void) {     int n, Q, d;     scanf( %d%d%d , &n, &Q, &d);     for (int i = 0; i < n; ++i) scanf( %d , &a[i]);     deque<int> q;     for (int i = 0; i < n; ++i) {       while (q.size() && q.front() <= i - d) q.pop_front();       while (q.size() && a[q.back()] >= a[i]) q.pop_back();       q.push_back(i);       f[i] = a[q.front()];     }     for (int i = 0; i < n; ++i) {       int t = i % d;       slv[t].a.push_back(f[i]);       slv[t].b.push_back(a[i]);     }     for (int i = 1; i <= Q; ++i) {       int l, r;       scanf( %d%d , &l, &r);       --l;       --r;       int t = l % d;       if (r % d < l % d) r -= d;       l /= d;       r /= d;       slv[t].qs.emplace_back(i, l, r);     }     for (int i = 0; i < d; ++i) slv[i].solve();     for (int i = 1; i <= Q; ++i) printf( %lld n , res[i]);     return 0;   }   