func_code_string: #include <bits/stdc++.h>   using namespace std;   template <class T>   bool umin(T& a, T b) {     if (a > b) {       a = b;       return 1;     }     return 0;   }   template <class T>   bool umax(T& a, T b) {     if (a < b) {       a = b;       return 1;     }     return 0;   }   int arr[300009], b[300009];   vector<pair<int, int> > adj[300009], query[300009];   const int N = 500;   long long ans[300009], par[300009];   int main() {     int n, q, k;     scanf( %d%d%d , &n, &q, &k);     deque<pair<int, int> > deq;     for (int i = 1; i <= n; i++) {       scanf( %d , arr + i);       while (!deq.empty() and deq.back().first >= arr[i]) deq.pop_back();       while (!deq.empty() and i - deq.front().second > k) deq.pop_front();       deq.push_back(make_pair(arr[i], i));       b[i] = deq.front().first;     }     for (int i = 1; i <= n; i++) adj[i % k].push_back(make_pair(i, b[i]));     if (k > N) {       while (q--) {         int l, r;         scanf( %d%d , &l, &r);         int mn = 1000000007;         long long res = arr[l];         int pos = upper_bound(adj[l % k].begin(), adj[l % k].end(),                               make_pair(l, 1000000007)) -                   adj[l % k].begin();         while (pos < (int)adj[l % k].size() and adj[l % k][pos].first <= r)           umin(mn, adj[l % k][pos++].second), res += mn;         printf( %lld n , res);       }       return 0;     }     for (int i = 1; i <= q; i++) {       int l, r;       scanf( %d%d , &l, &r);       query[l].push_back(make_pair(r, i));       ans[i] = arr[l];     }     for (int i = 0; i < k; i++) {       memset(par, 0, sizeof par);       int sz = adj[i].size();       vector<pair<int, int> > v;       for (int j = sz - 1; j >= 0; j--) {         int l = adj[i][j].first, val = adj[i][j].second;         if (!v.empty()) {           for (int h = 0; h < int(query[l].size()); h++) {             int r = query[l][h].first;             int idx = query[l][h].second;             int R = upper_bound(adj[i].begin(), adj[i].end(),                                 make_pair(r, 1000000007)) -                     adj[i].begin();             int st = 0, en = v.size() - 1;             while (st + 1 < en) {               int mid = (st + en) >> 1;               if (v[mid].second < R)                 en = mid;               else                 st = mid;             }             if (v[st].second < R) en = st;             int who = v[en].second;             int me = v[en].first;             if (who < R)               ans[idx] += par[v.back().second] - par[who] + (R - who) * 1LL * me;           }         }         while (!v.empty() and v.back().first >= val) v.pop_back();         if (!v.empty()) {           int next_ind = v.back().second;           par[j] = par[next_ind] + (next_ind - j) * 1LL * val;         }         v.push_back(make_pair(val, j));       }     }     for (int i = 1; i <= q; i++) printf( %lld n , ans[i]);     return 0;   }   