Problem: Vasya the carpenter has an estate that is separated from the wood by a fence. The fence consists of n planks put in a line. The fence is not closed in a circle. The planks are numbered from left to right from 1 to n, the i-th plank is of height ai. All planks have the same width, the lower edge of each plank is located at the ground level.

Recently a local newspaper "Malevich and Life" wrote that the most fashionable way to decorate a fence in the summer is to draw a fuchsia-colored rectangle on it, the lower side of the rectangle must be located at the lower edge of the fence.

Vasya is delighted with this idea! He immediately bought some fuchsia-colored paint and began to decide what kind of the rectangle he should paint. Vasya is sure that the rectangle should cover k consecutive planks. In other words, he will paint planks number x, x + 1, ..., x + k - 1 for some x (1 ≤ x ≤ n - k + 1). He wants to paint the rectangle of maximal area, so the rectangle height equals min ai for x ≤ i ≤ x + k - 1, x is the number of the first colored plank.

Vasya has already made up his mind that the rectangle width can be equal to one of numbers of the sequence k1, k2, ..., km. For each ki he wants to know the expected height of the painted rectangle, provided that he selects x for such fence uniformly among all n - ki + 1 possible values. Help him to find the expected heights.

Input

The first line contains a single integer n (1 ≤ n ≤ 106) — the number of planks in the fence. The second line contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109) where ai is the height of the i-th plank of the fence.

The third line contains an integer m (1 ≤ m ≤ 106) and the next line contains m space-separated integers k1, k2, ..., km (1 ≤ ki ≤ n) where ki is the width of the desired fuchsia-colored rectangle in planks.

Output

Print m whitespace-separated real numbers, the i-th number equals the expected value of the rectangle height, if its width in planks equals ki. The value will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Examples

Input

3
3 2 1
3
1 2 3


Output

2.000000000000000
1.500000000000000
1.000000000000000


Input

2
1 1
3
1 2 1


Output

1.000000000000000
1.000000000000000
1.000000000000000

Note

Let's consider the first sample test. 

  * There are three possible positions of the fence for k1 = 1. For the first position (x = 1) the height is 3, for the second one (x = 2) the height is 2, for the third one (x = 3) the height is 1. As the fence position is chosen uniformly, the expected height of the fence equals <image>; 
  * There are two possible positions of the fence for k2 = 2. For the first position (x = 1) the height is 2, for the second one (x = 2) the height is 1. The expected height of the fence equals <image>; 
  * There is the only possible position of the fence for k3 = 3. The expected height of the fence equals 1. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 1e6 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
int n, lef[MX], rig[MX];
long long ans[MX];
pair<long long, long long> cum[MX];
vector<int> a;
pair<long long, long long>& operator+=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = {l.first + r.first, l.second + r.second};
}
pair<long long, long long>& operator-=(pair<long long, long long>& l,
                                       const pair<long long, long long>& r) {
  return l = {l.first - r.first, l.second - r.second};
}
void ad(int l, int r, int c, pair<long long, long long> p) {
  p.first *= c, p.second *= c;
  cum[l] += p;
  cum[r + 1] -= p;
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  re(n);
  a.resize(n);
  re(a);
  vector<pair<int, int> > v;
  v.push_back({0, -1});
  for (int i = (0); i < (n); ++i) {
    while (v.back().first > a[i]) v.pop_back();
    lef[i] = v.back().second;
    v.push_back({a[i], i});
  }
  v = {{0, n}};
  for (int i = (n)-1; i >= (0); --i) {
    while (v.back().first >= a[i]) v.pop_back();
    rig[i] = v.back().second;
    v.push_back({a[i], i});
  }
  for (int i = (0); i < (n); ++i) {
    lef[i]++, rig[i]--;
    int t = rig[i] - lef[i];
    ad(0, i - lef[i], a[i], {1 - i, 1});
    ad(i - lef[i] + 1, t, a[i], {1 - lef[i], 0});
    ad(0, rig[i] - i, a[i], {i, 0});
    ad(rig[i] - i + 1, t, a[i], {rig[i], -1});
  }
  for (int i = (0); i < (n); ++i) {
    if (i) cum[i] += cum[i - 1];
    ans[i] = cum[i].first + cum[i].second * i;
  }
  int m;
  re(m);
  for (int i = (0); i < (m); ++i) {
    int k;
    re(k);
    cout << fixed << setprecision(12) << (long double)ans[k - 1] / (n + 1 - k)
         << "\n";
  }
}