M. V-Diagram
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

A $$$1$$$-indexed integer sequence $$$a$$$ of length $$$n$$$ is a V-diagram if $$$n \ge 3$$$ and there exists an index $$$i$$$ ($$$1 \lt i \lt n$$$) satisfying the following:

  • $$$a_j \gt a_{j + 1}$$$ for $$$1 \le j \lt i$$$;
  • $$$a_j \gt a_{j - 1}$$$ for $$$i \lt j \le n$$$.

Given a V-diagram $$$a$$$, find a V-diagram $$$b$$$ with the maximum possible average such that $$$b$$$ is a consecutive subsequence of $$$a$$$.

A consecutive subsequence of a sequence can be obtained by removing some (possibly zero) elements from the beginning and end of the sequence.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) denoting the number of test cases. For each test case:

The first line contains one integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) denoting the length of the integer sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) denoting the sequence $$$a$$$ itself.

It is guaranteed that $$$a$$$ is a V-diagram, and the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a real number denoting the maximum possible average.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer will be considered correct if and only if $$$\frac{|x - y|}{\max(1, |y|)} \le 10^{-9}$$$.

Example
Input
2
4
8 2 7 10
6
9 6 5 3 4 8
Output
6.75000000000000000000
5.83333333333333303727