木匠 Vasya 拥有一处庄园,用栅栏将其与木材隔开。栅栏由 n 块排成一行的木板组成。栅栏不是封闭成一个圆圈的。木板从左到右编号为 1 到 n,第 i 块木板的高度为 ai。所有木板的宽度相同,每块木板的下边缘位于地面。
近日,当地报纸《马列维奇与生活》撰文称,夏季装饰栅栏最时尚的方式是在栅栏上画一个紫红色的矩形,矩形的下边必须位于栅栏的下边缘。
Vasya 对这个想法很满意!他立即买了一些紫红色的颜料,开始决定要画一个什么样的矩形。 Vasya 确信该矩形应覆盖 k 个连续的木板。换句话说,对于某些 x (1 ≤ x ≤ n - k + 1),他将绘制编号为 x, x + 1, ..., x + k - 1 的木板。他要绘制面积最大的矩形,因此矩形高度等于 min ai,其中 x ≤ i ≤ x + k - 1,x 是第一块着色木板的编号。
Vasya 已经决定矩形宽度可以等于序列 k1, k2, ..., km 中的数字之一。对于每个 ki,他想知道所绘制矩形的预期高度,前提是他在所有 n - ki + 1 个可能值中统一为此类栅栏选择 x。帮助他找到预期的高度。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106) — 栅栏中的木板数量。第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是栅栏第 i 块木板的高度。
第三行包含一个整数 m (1 ≤ m ≤ 106),下一行包含 m 个空格分隔的整数 k1, k2, ..., km (1 ≤ ki ≤ n),其中 ki 是木板中所需的紫红色矩形的宽度。
输出
打印 m 个以空格分隔的实数,如果矩形的宽度等于 ki,则第 i 个数字等于矩形高度的预期值。如果绝对误差或相对误差不超过 10 - 9,则该值被认为是正确的。
示例
输入 #1
3 3 2 1 3 1 2 3
输出 #1
2.000000000000000 1.500000000000000 1.000000000000000
输入 #2
2 1 1 3 1 2 1
输出 #2
1.000000000000000 1.000000000000000 1.000000000000000
注意
让我们考虑第一个示例测试。
- k1 = 1时,栅栏有三个可能的位置。对于第一个位置(x = 1),高度为3,对于第二个位置(x = 2),高度为2,对于第三个位置(x = 3),高度为1。由于栅栏位置是统一选择的,栅栏的期望高度等于$$\frac{3+2+1}{3}=2$$;
- 对于 k2 = 2,栅栏有两个可能的位置。对于第一个位置 (x = 1),高度为 2,对于第二个位置 (x = 2),高度为 1。栅栏的预期高度等于 $${ \frac { 2 + 1 } { 2 } } = 1。 5$$;
- k3 = 3 时栅栏唯一可能的位置。栅栏的预期高度等于 1。