CF212D Cutting a Fence

木匠 Vasya 有一块被篱笆与树林隔开的庄园。这段篱笆由 $n$ 块木板首尾相连组成。篱笆不是首尾相接成圆环的。木板从左到右编号为 $1$ 到 $n$，第 $i$ 块木板的高度为 $a_i$。所有木板宽度相同，每块木板的下边沿都与地面齐平。 最近，地方报纸《Malevich and Life》报道说，今夏最时尚的篱笆装饰方式是画一个紫红色矩形，这个矩形的下边必须位于篱笆的下边沿。 Vasya 很喜欢这个主意！他马上买来了紫红色油漆并开始决定要画什么样的矩形。Vasya 认为，矩形应覆盖 $k$ 块连续的木板。换句话说，他会选择编号为 $x$、$x+1$、...、$x+k-1$ 的木板进行涂色，$x$ 满足 $1 \le x \le n-k+1$。他希望绘制面积最大的矩形，所以此矩形的高度应为 $min\,a_i$，其中 $x \le i \le x+k-1$，$x$ 即为第一块被涂色木板的编号。 Vasya 已经决定，矩形的宽度可以为数列 $k_1,k_2,\ldots,k_m$ 中的任意一个。对每个 $k_i$，他都想知道在涂色起点 $x$ 在 $n-k_i+1$ 个可能的位置中等概率选取时，绘制矩形高度的期望值。请你帮他计算这些期望高度。

第一行包含一个整数 $n$ $(1 \le n \le 10^6)$，表示篱笆上的木板数。第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，$1 \le a_i \le 10^9$，表示每块木板的高度。 第三行包含一个整数 $m$ $(1 \le m \le 10^6)$，下一行包含 $m$ 个空格分隔的整数 $k_1,k_2,\ldots,k_m$ $(1 \le k_i \le n)$，表示矩形的宽度（以木板块数计）。

输出 $m$ 个用空格分隔的实数，第 $i$ 个数表示当矩形宽度为 $k_i$ 块木板时，绘制矩形高度的期望值。只要其绝对误差或相对误差不超过 $10^{-9}$ 即为正确。

下面以第一个样例说明： - 对于 $k_1=1$，篱笆有三种可能的位置：第一个位置 $(x=1)$ 时高度为 3，第二个位置 $(x=2)$ 时高度为 2，第三个位置 $(x=3)$ 时高度为 1。由于选择位置是等概率的，因此该情况下的期望高度为 $\frac{3+2+1}{3}$。 - 对于 $k_2=2$，有两种可能的位置：第一个位置 $(x=1)$ 时高度为 2，第二个位置 $(x=2)$ 时高度为 1。期望高度为 $\frac{2+1}{2}$。 - 对于 $k_3=3$，只有一种可能的位置。期望高度为 1。 由 ChatGPT 5 翻译