func_code_string: #include <bits/stdc++.h>   using namespace std;   struct BIT {     long long T[1000100];     long long ALL;     BIT() { ALL = 0; }     void add(int pos, long long w) {       ++pos;       ALL += w;       for (; pos < 1000100; pos += (pos & (-pos))) T[pos] += w;     }     long long all_from(int pos) {       long long ret = ALL;       for (; pos > 0; pos -= pos & (-pos)) ret -= T[pos];       return ret;     }   };   int N, M, H[1000100], FL[1000100], FR[1000100];   stack<int> pos;   vector<int> ib, ie, spl, spr, val;   vector<int> ids;   inline bool icompare(const int& f, const int& s) {     return ie[f] - ib[f] > ie[s] - ib[s];   }   vector<double> ans;   vector<int> Q, qid;   inline bool qcompare(const int& f, const int& s) { return Q[f] > Q[s]; }   BIT rem_val, rem_sum;   int main() {     scanf( %d , &N);     H[0] = H[N + 1] = -1100000000;     for (int i = 0; i < N; ++i) scanf( %d , &H[i + 1]);     pos.push(0);     for (int i = 1; i <= N; ++i) {       while (H[pos.top()] > H[i]) pos.pop();       FL[i] = pos.top();       pos.push(i);     }     while (!pos.empty()) pos.pop();     pos.push(N + 1);     for (int i = N; i > 0; --i) {       while (H[pos.top()] >= H[i]) pos.pop();       FR[i] = pos.top();       pos.push(i);     }     for (int i = 1; i <= N; ++i) {       ib.push_back(FL[i] + 1);       ie.push_back(FR[i] - 1);       val.push_back(H[i]);       spl.push_back(i - FL[i] - 1);       spr.push_back(FR[i] - i - 1);     }     for (int i = 0; i < ((int)(ib).size()); ++i) ids.push_back(i);     sort(ids.begin(), ids.end(), icompare);     scanf( %d , &M);     ans.resize(M);     Q.resize(M);     for (int i = 0; i < M; ++i) qid.push_back(i);     for (int i = 0; i < M; ++i) scanf( %d , &Q[i]);     sort(qid.begin(), qid.end(), qcompare);     long long val_all = 0, sum_all = 0;     int cur = 0;     for (int i = 0; i < ((int)(qid).size()); ++i) {       int V = Q[qid[i]];       while (cur < ((int)(ids).size()) && ie[ids[cur]] - ib[ids[cur]] + 1 >= V) {         int T = ids[cur++];         val_all += val[T] * 1LL * (ie[T] - ib[T] + 1);         sum_all += val[T];         if (spl[T] > 0)           rem_val.add(spl[T], spl[T] * 1LL * val[T]), rem_sum.add(spl[T], val[T]);         if (spr[T] > 0)           rem_val.add(spr[T], spr[T] * 1LL * val[T]), rem_sum.add(spr[T], val[T]);       }       long long out = val_all - (V - 1) * sum_all;       out -= rem_val.all_from(V) - (V - 1) * rem_sum.all_from(V);       ans[qid[i]] = ((double)out) / (N - V + 1);     }     for (int i = 0; i < M; ++i) printf( %.12lf n , ans[i]);     return 0;   }   