CF212D.Cutting a Fence

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 a__i. 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 a__i 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 _k_1, _k_2, ..., k__m. For each k__i he wants to know the expected height of the painted rectangle, provided that he selects x for such fence uniformly among all n - k__i + 1 possible values. Help him to find the expected heights.

木匠瓦夏拥有一处庄园，庄园与树林之间由一道篱笆隔开。这道篱笆由排成一行的 $n$ 块木板组成，篱笆并非围成环形。木板从左到右依次编号为 $1$ 至 $n$，其中第 $i$ 块木板的高度为 $a_i$。所有木板宽度相同，且每块木板的底边均位于地面高度。

最近，当地报纸《马列维奇与生活》刊文指出：今夏装饰篱笆最时尚的方式，是在其上绘制一个紫红色矩形，该矩形的底边必须与篱笆底边重合。

瓦夏对这一创意欣喜若狂！他立刻购买了紫红色油漆，并开始思考应绘制怎样的矩形。瓦夏确信：该矩形必须覆盖 $k$ 块连续的木板。换言之，他将涂刷编号为 $x,\,x+1,\,\dots,\,x+k-1$ 的木板（其中 $x$ 满足 $1 \le x \le n - k + 1$）。他希望所绘矩形面积最大，因此矩形高度等于 $\min a_i$（其中 $x \le i \le x + k - 1$），而 $x$ 是被涂刷木板的起始编号。

瓦夏已决定：矩形的宽度只能取序列 $k_1,\,k_2,\,\dots,\,k_m$ 中的某个值。对于每个 $k_i$，他希望知道所绘矩形的期望高度，即在所有 $n - k_i + 1$ 种可能的起始位置 $x$ 中，等概率随机选取 $x$ 时，对应矩形高度的数学期望值。请帮助他求出这些期望高度。

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 _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) where a__i 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 _k_1, _k_2, ..., k__m (1 ≤ k__i ≤ n) where k__i is the width of the desired fuchsia-colored rectangle in planks.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 表示围栏中木板的数量。
第二行包含一个整数序列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示围栏中第 $i$ 块木板的高度。

第三行包含一个整数 $m$（$1 \leq m \leq 10^6$），下一行包含 $m$ 个以空格分隔的整数 $k_1, k_2, \dots, k_m$（$1 \leq k_i \leq n$），其中 $k_i$ 表示所期望的紫红色矩形在木板宽度方向上的跨度（以木板数量为单位）。

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

输出 m 个以空格分隔的实数，其中第 i 个数等于矩形高度的期望值（此时该矩形的宽度为 k__i 块木板）。若该值的绝对误差或相对误差均不超过 $10^{-9}$，则视为正确。

Let's consider the first sample test.

• There are three possible positions of the fence for _k_1 = 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 ;
• There are two possible positions of the fence for _k_2 = 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 ;
• There is the only possible position of the fence for _k_3 = 3. The expected height of the fence equals 1.

我们来考虑第一个样例测试。

• 当 $k_1 = 1$ 时，围栏有三种可能的位置。第一种位置（$x = 1$）对应的高度为 $3$，第二种位置（$x = 2$）对应的高度为 $2$，第三种位置（$x = 3$）对应的高度为 $1$。由于围栏位置是均匀随机选择的，围栏高度的期望值为 ；
• 当 $k_2 = 2$ 时，围栏有两种可能的位置。第一种位置（$x = 1$）对应的高度为 $2$，第二种位置（$x = 2$）对应的高度为 $1$。围栏高度的期望值为 ；
• 当 $k_3 = 3$ 时，围栏只有一种可能的位置。围栏高度的期望值为 $1$。