#include #include #include #include typedef struct binary_heap { void *array; size_t heap_size; size_t max_size; size_t val_size; int (*cmp) (const void *, const void *); } heap; heap* new_binary_heap (const size_t val_size, int (*cmp_func) (const void *, const void *)) { heap *h = (heap *) calloc (1, sizeof (heap)); h->array = malloc (val_size * (1 + 1)); h->heap_size = 0; h->max_size = 1; h->val_size = val_size; h->cmp = cmp_func; return h; } static inline void heap_func_swap (void * restrict a, void * restrict b, size_t val_size) { if ((val_size & 7) == 0) { uint64_t *p = (uint64_t *) a; uint64_t *q = (uint64_t *) b; val_size /= sizeof (uint64_t); while (val_size--) { const uint64_t tmp = *p; *p++ = *q; *q++ = tmp; } } else { uint8_t *p = (uint8_t *) a; uint8_t *q = (uint8_t *) b; while (val_size--) { const uint8_t tmp = *p; *p++ = *q; *q++ = tmp; } } } static inline void heap_func_copy (void * restrict dst, const void * restrict src, size_t val_size) { if ((val_size & 7) == 0) { const uint64_t *p = (const uint64_t *) src; uint64_t *q = (uint64_t *) dst; val_size /= sizeof (uint64_t); while (val_size--) { *q++ = *p++; } } else { const uint8_t *p = (const uint8_t *) src; uint8_t *q = (uint8_t *) dst; while (val_size--) { *q++ = *p++; } } } void push (heap * const h, const void *val) { if (h->heap_size == h->max_size) { h->max_size = 2 * h->max_size + 1; h->array = realloc (h->array, h->val_size * (h->max_size + 1)); } h->heap_size++; uint8_t * const array = (uint8_t *) h->array; size_t k = h->heap_size; const size_t val_size = h->val_size; int (* const cmp) (const void *, const void *) = h->cmp; heap_func_copy(array + k * val_size, val, val_size); while (k > 1) { size_t parent = k / 2; if (cmp (array + parent * val_size, array + k * val_size) <= 0) { return; } heap_func_swap (array + parent * val_size, array + k * val_size, val_size); k = parent; } } void pop (heap * const h, void *res) { uint8_t * const array = (uint8_t *) h->array; const size_t val_size = h->val_size; if (res != NULL) { heap_func_copy (res, array + val_size, val_size); } heap_func_copy (array + val_size, array + val_size * h->heap_size, val_size); h->heap_size--; int (* const cmp) (const void *, const void *) = h->cmp; const size_t n = h->heap_size; size_t k = 1; while (2 * k + 1 <= n) { const int c = cmp (array + val_size * 2 * k, array + val_size * (2 * k + 1)); const size_t next = 2 * k + (c <= 0 ? 0 : 1); if (cmp (array + val_size * k, array + val_size * next) <= 0) return; heap_func_swap (array + val_size * k, array + val_size * next, val_size); k = next; } if (2 * k <= n && cmp (array + val_size * k, array + val_size * 2 * k) > 0) { heap_func_swap (array + val_size * k, array + val_size * 2 * k, val_size); } } typedef int32_t i32; typedef int64_t i64; #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) typedef struct { i32 len; i32 k; } node; int cmp_node (const void *a, const void *b) { const node *p = a; const node *q = b; i64 d = (i64) p->len * q->k - p->k * q->len; return d == 0 ? 0 : d > 0 ? -1 : 1; } void run (void) { i32 n; scanf ("%" SCNi32, &n); heap *h = new_binary_heap (sizeof (node), cmp_node); while (n--) { i32 l; scanf ("%" SCNi32, &l); push (h, &(node){l, 1}); } const i32 m = 500000; double *ans = ALLOC (m + 1, double); for (i32 i = 1; i <= m; ++i) { node t; pop (h, &t); ans[i] = (double) t.len / t.k; t.k++; push (h, &t); } i32 q; scanf ("%" SCNi32, &q); while (q--) { i32 x; scanf ("%" SCNi32, &x); printf ("%.9f\n", ans[x]); } } int main (void) { run(); return 0; }