There are two friends Alice and Bob. They have a packet of $n$ candies. They want to split the candies between them, and to do so, they kept them all in a single line. The $i^{\text{th}}$ candy in the line has a sweetness value of $a_i$. They decided to take turns in picking the candies. Alice has the first turn. In a person's turn, they either eat the leftmost candy or the rightmost candy with equal probability.
Can you find the expected value of sum of sweetness of the candies eaten by Alice?
Your answer is considered correct if its absolute or relative error doesn't exceed $10^{-6}$ .

-----Input:-----
- The first line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains a single integer $n$ denoting the number of candies.
- Second line of each testcase contains  $n$ space separated integers representing $a_1,a_2,a_3,...a_n$ respectively.

-----Output:-----
For each testcase, output the expected value of sum of sweetness of the candies which Alice eats.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq n \leq 10^3$
- $1 \leq a_i \leq 10^6$
- Sum of $n$ across all the tests $\leq 10^3$

-----Sample Input:-----
2
2
1 2
3
1 2 3

-----Sample Output:-----
1.500000000000000
4.000000000000000

-----EXPLANATION:-----
In the first sample, Alice eats either the first or the second candy with equal probability. Hence, expected value is $(1+2)/2 = 1.5$
For the second sample, expected value is $4$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def recSolve(a, dp, l, r):\n if(l>r):\n  return 0\n if dp[l][r] != 0.0:\n  return dp[l][r]\n x = a[l]+ (recSolve(a, dp, l+2, r) + recSolve(a, dp, l+1, r-1))*0.5\n y = a[r]+ (recSolve(a, dp, l+1, r-1) + recSolve(a, dp, l, r-2))*0.5\n dp[l][r] = (x+y)*0.5\n return dp[l][r]\nfor _ in range(int(input())):\n n = int(input())\n a = list(map(int, input().split()))\n dp = [[0.0]*(n+1) for i in range(n+1)]\n res = recSolve(a, dp, 0, n-1)\n print(res)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13195