func_code_string: #include <bits/stdc++.h>   using namespace std;   int R[300010 * 2], L[300010 * 2], n, m, sum[300010], sz;   struct Fun {     int k, b;   } f[300010], id[300010 * 20], s[300010];   inline int Read() {     char c = getchar();     int num = 0, f = 1;     while ( 0  > c || c >  9 ) {       if (c ==  - ) f = -1;       c = getchar();     }     while ( 0  <= c && c <=  9 ) num = num * 10 + c -  0 , c = getchar();     return (num * f);   }   inline bool Pd(Fun c, Fun a, Fun b) {     return ((long long)(c.b - a.b) * (b.k - c.k) <=             (long long)(c.b - b.b) * (a.k - c.k));   }   inline void Ins(int rt, Fun x) {     id[++sz] = x;     if (!R[rt]) L[rt] = sz;     R[rt] = sz;     while (R[rt] - L[rt] >= 2 && Pd(id[R[rt] - 2], id[R[rt] - 1], id[R[rt]])) {       id[R[rt] - 1] = id[R[rt]];       id[R[rt]] = (Fun){0, 0};       sz--;       R[rt]--;     }   }   inline void Merge(int rt, int l, int mid, int r) {     int i = l, j = mid + 1, k = l - 1;     while (i <= mid && j <= r) {       if ((f[i].k < f[j].k) || (f[i].k == f[j].k && f[i].b < f[j].b))         s[++k] = f[i], i++;       else         s[++k] = f[j], j++;     }     for (; j <= r; j++) s[++k] = f[j];     for (; i <= mid; i++) s[++k] = f[i];     f[l] = s[l];     Ins(rt, f[l]);     for (int t = l + 1; t <= r; t++) {       f[t] = s[t];       if (f[t].k != f[t - 1].k) Ins(rt, f[t]);     }   }   inline void Build(int rt, int l, int r) {     int mid = (l + r) / 2;     if (l == r) {       Ins(rt, f[l]);       return;     }     Build(rt * 2, l, mid);     Build(rt * 2 + 1, mid + 1, r);     Merge(rt, l, mid, r);   }   inline int Cal(int l, int r, int x) {     while (r - l > 1) {       int mid = (l + r) / 2;       if (id[mid].k * x + id[mid].b < id[mid + 1].k * x + id[mid + 1].b) {         r = mid;         continue;       }       if (id[mid].k * x + id[mid].b > id[mid + 1].k * x + id[mid + 1].b) {         l = mid;         continue;       }       if (id[mid].k * x + id[mid].b < id[mid - 1].k * x + id[mid - 1].b) {         l = mid;         continue;       }       if (id[mid].k * x + id[mid].b > id[mid - 1].k * x + id[mid - 1].b) {         r = mid;         continue;       }     }     return (min(id[l].k * x + id[l].b, id[r].k * x + id[r].b));   }   inline int Find(int rt, int l, int r, int a, int b, int p) {     int mid = (l + r) / 2;     if (l == a && r == b) {       if (l <= 115 && 115 <= r) int deb = 0;       return (Cal(L[rt], R[rt], p));     }     if (b <= mid) return (Find(rt * 2, l, mid, a, b, p));     if (mid < a) return (Find(rt * 2 + 1, mid + 1, r, a, b, p));     if (a <= mid && mid < b) {       int L = Find(rt * 2, l, mid, a, mid, p);       int R = Find(rt * 2 + 1, mid + 1, r, mid + 1, b, p);       return (min(L, R));     }   }   int main() {     n = Read();     for (int i = 1; i <= n; i++) f[i].k = Read();     for (int i = 1; i <= n; i++)       sum[i] = sum[i - 1] + f[i].k, f[i].b = f[i].k * i - sum[i];     Build(1, 1, n);     m = Read();     for (int i = 1; i <= m; i++) {       int x = Read(), y = Read();       int Min = Find(1, 1, n, y - x + 1, y, x - y);       printf( %d n , min(sum[y] - sum[y - x], sum[y] + Min));     }   }   