#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n == 1) {
    return false;
  } else if (n == 2 || n == 3) {
    return true;
  } else {
    for (long long i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
        return false;
      }
    }
  }
  return true;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  } else {
    return gcd(b % a, a);
  }
}
long long lcm(long long a, long long b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
bool isEven(long long a) {
  if (a % 2 == 0) {
    return true;
  }
  return false;
}
bool isSquare(long long x) {
  long long n1 = sqrt(x);
  double n2 = sqrt(x);
  if (n2 - n1 == 0) {
    return true;
  }
  return false;
}
bool isPowerOfTwo(int x) { return x && (!(x & (x - 1))); }
void solve(void) {
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long arr[n];
    for (long long i = 0; i < n; i++) {
      cin >> arr[i];
    }
    sort(arr, arr + n, greater<long long>());
    double sum = 0;
    for (long long i = 0; i < n; i++) {
      sum += arr[i];
    }
    double ansi = 0;
    double ans = INT_MIN;
    for (long long i = 0; i < n; i++) {
      ansi += arr[i];
      ans = max(ans, ansi / (i + 1) + (sum - ansi) / (n - i - 1));
    }
    cout << fixed << setprecision(9) << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  solve();
}

### Prompt

Please formulate a Cpp solution to the following problem:

Ezzat has an array of n integers (maybe negative). He wants to split it into two non-empty subsequences a and b, such that every element from the array belongs to exactly one subsequence, and the value of f(a) + f(b) is the maximum possible value, where f(x) is the average of the subsequence x. 

A sequence x is a subsequence of a sequence y if x can be obtained from y by deletion of several (possibly, zero or all) elements.

The average of a subsequence is the sum of the numbers of this subsequence divided by the size of the subsequence.

For example, the average of [1,5,6] is (1+5+6)/3 = 12/3 = 4, so f([1,5,6]) = 4.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^3)— the number of test cases. Each test case consists of two lines.

The first line contains a single integer n (2 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (-10^9 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 3⋅10^5.

Output

For each test case, print a single value — the maximum value that Ezzat can achieve.

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

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input


4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3


Output


4.500000000
-12.500000000
4.000000000
18.666666667

Note

In the first test case, the array is [3, 1, 2]. These are all the possible ways to split this array: 

  * a = [3], b = [1,2], so the value of f(a) + f(b) = 3 + 1.5 = 4.5. 
  * a = [3,1], b = [2], so the value of f(a) + f(b) = 2 + 2 = 4. 
  * a = [3,2], b = [1], so the value of f(a) + f(b) = 2.5 + 1 = 3.5. 

Therefore, the maximum possible value 4.5.

In the second test case, the array is [-7, -6, -6]. These are all the possible ways to split this array: 

  * a = [-7], b = [-6,-6], so the value of f(a) + f(b) = (-7) + (-6) = -13. 
  * a = [-7,-6], b = [-6], so the value of f(a) + f(b) = (-6.5) + (-6) = -12.5. 

Therefore, the maximum possible value -12.5.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n == 1) {
    return false;
  } else if (n == 2 || n == 3) {
    return true;
  } else {
    for (long long i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
        return false;
      }
    }
  }
  return true;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  } else {
    return gcd(b % a, a);
  }
}
long long lcm(long long a, long long b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
bool isEven(long long a) {
  if (a % 2 == 0) {
    return true;
  }
  return false;
}
bool isSquare(long long x) {
  long long n1 = sqrt(x);
  double n2 = sqrt(x);
  if (n2 - n1 == 0) {
    return true;
  }
  return false;
}
bool isPowerOfTwo(int x) { return x && (!(x & (x - 1))); }
void solve(void) {
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    long long arr[n];
    for (long long i = 0; i < n; i++) {
      cin >> arr[i];
    }
    sort(arr, arr + n, greater<long long>());
    double sum = 0;
    for (long long i = 0; i < n; i++) {
      sum += arr[i];
    }
    double ansi = 0;
    double ans = INT_MIN;
    for (long long i = 0; i < n; i++) {
      ansi += arr[i];
      ans = max(ans, ansi / (i + 1) + (sum - ansi) / (n - i - 1));
    }
    cout << fixed << setprecision(9) << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  solve();
}

```