func_code_string: #include <bits/stdc++.h>   using namespace std;   class ConvexHullTrick {    public:     vector<long long int> a, b;     int size = -1;     bool can_remove(int a, int b, int c, int d) {       if (a / b != c / d) return a / b < c / d;       a %= b;       c %= d;       if (a == 0) return true;       if (c == 0) return false;       return can_remove(d, c, b, a);     }     void add(long long int i, long long int j) {       size++;       a.push_back(i);       b.push_back(j);       while (size >= 2 &&              can_remove(b[size - 1] - b[size], a[size] - a[size - 1],                         b[size - 2] - b[size - 1], a[size - 1] - a[size - 2])) {         a.erase(a.end() - 2);         b.erase(b.end() - 2);         size--;       }     }     double iniInterval(int i) {       if (i == 0) return -1000000010;       return ((double)b[i] - b[i - 1]) / (a[i - 1] - a[i]);     }     long long int query(int x) {       int i = 0, j = size;       while (i < j) {         int m = (i == j - 1) ? j : (i + j) / 2;         if (iniInterval(m) <= (double)x)           i = m;         else           j = m - 1;       }       return a[i] * x + b[i];     }   };   struct node {     int ini, fim;     ConvexHullTrick CHT;   } SEG[4 * 100010];   int n, q, n1, n2;   int v[100010];   long long int sv[100010];   void merge(int i, int f1, int f2) {     int p = 0, q = 0;     for (; p <= SEG[f1].CHT.size && q <= SEG[f2].CHT.size;) {       long long int a1 = SEG[f1].CHT.a[p];       long long int b1 = SEG[f1].CHT.b[p];       long long int a2 = SEG[f2].CHT.a[q];       long long int b2 = SEG[f2].CHT.b[q];       if (a1 == a2) {         SEG[i].CHT.add(a1, min(b1, b2));         p++;         q++;       } else if (a1 > a2) {         SEG[i].CHT.add(a1, b1);         p++;       } else {         SEG[i].CHT.add(a2, b2);         q++;       }     }     for (; p <= SEG[f1].CHT.size;) {       SEG[i].CHT.add(SEG[f1].CHT.a[p], SEG[f1].CHT.b[p]);       p++;     }     for (; q <= SEG[f2].CHT.size;) {       SEG[i].CHT.add(SEG[f2].CHT.a[q], SEG[f2].CHT.b[q]);       q++;     }   }   void build(int id, int i, int j) {     SEG[id].ini = i;     SEG[id].fim = j;     if (i == j) return void(SEG[id].CHT.add(v[i], v[i] * i - sv[i]));     int m = (i + j) / 2;     build(2 * id, i, m);     build(2 * id + 1, m + 1, j);     merge(id, 2 * id, 2 * id + 1);   }   long long int query(int id, int i, int j, int k) {     if (SEG[id].ini > j || SEG[id].fim < i)       return ((long long int)1000000010) * 1000000010;     if (SEG[id].ini >= i && SEG[id].fim <= j) return SEG[id].CHT.query(k);     return min(query(2 * id, i, j, k), query(2 * id + 1, i, j, k));   }   int main() {     scanf( %d , &n);     for (int g = 1; g <= n; g++) {       scanf( %d , &v[g]);       sv[g] = sv[g - 1] + v[g];     }     build(1, 1, n);     scanf( %d , &q);     for (int g = 0; g < q; g++) {       scanf( %d %d , &n1, &n2);       printf( %lld n , query(1, n2 - n1 + 1, n2, n1 - n2) + sv[n2]);     }   }   