발렌타인 데이
시간 제한2초메모리 제한512 MB
각 선물이 확률 Pi로 기쁨을 일으킬 때, 정확히 한 번만 기쁨이 일어날 확률이 최대가 되도록 선물의 부분집합을 고른다.
문제
Oipotato는 여자친구를 매우 사랑한다. 발렌타인 데이가 다가와서 여자친구에게 줄 선물을 사기로 했다.
가게에는 n개의 선물이 있고, Oipotato는 그중 일부를 골라 살 수 있다. 여자친구는 선물을 받으면 매우 행복해할 가능성이 있다. 따라서 Oipotato가 여자친구에게 k개의 선물을 주면, 여자친구가 매우 행복해할 기회가 k번 생긴다. 하지만 Oipotato는 선물 때문에 여자친구가 너무 여러 번 매우 행복해하는 것은 원하지 않는다.
정확히 말해, 선물 i는 확률 Pi로 Oipotato의 여자친구를 매우 행복하게 만든다. Oipotato는 여자친구가 정확히 한 번 매우 행복해할 확률을 최대로 만들기 위해 무엇을 살지 정해야 한다. 그 최대 확률을 구하는 것을 도와주자.
입력
여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 다음과 같다.
첫 줄에는 살 수 있는 선물의 수를 나타내는 정수 n (1 ≤ n ≤ 10 000)이 주어진다.
둘째 줄에는 소수점 아래 정확히 여섯 자리로 주어지는 n개의 실수 Pi (0 ≤ Pi ≤ 1)가 주어진다. Pi는 선물 i를 받았을 때 Oipotato의 여자친구가 매우 행복해할 확률이다.
모든 테스트 케이스에서 n의 합은 500 000을 넘지 않는다.
출력
각 테스트 케이스마다 정답을 한 줄에 출력한다. 절대 오차가 10−6 미만이면 정답으로 인정된다.