주식 거래

주식 투자를 시작한 당신에게 내부자가 알려주길, 앞으로 N일 동안 이 주식에 배정될 N개의 가격(달러) 목록이 있다고 한다. 이 목록의 각 가격은 앞으로의 N일 중 정확히 하루에 배정되며, 같은 날의 가격은 변하지 않는다. 내부자 친구가 원하는 대로 배정해 주겠다고 했으므로, 이익을 최대로 만들도록 가격을 날짜에 배정하려 한다.

N개의 가격을 N일에 모두 배정했다고 하자. 1일이 시작되기 전에 당신은 이 주식 1단위를 가지고 있고 돈은 한 푼도 없다. 이후 N일 동안 매일, 그날 배정된 가격으로 가지고 있는 주식의 일부 또는 전부를 팔아 달러를 받거나, 살 수 있는 주식의 일부 또는 전부를 사서 달러를 지불할 수 있다. 아무것도 하지 않아도 된다. 각 날에는 주식이 무한히 공급된다고 가정한다.

최종 이익은 당신이 가진 돈의 양이므로, N일이 끝날 때까지 모든 주식을 팔아야 한다.

가격 목록이 주어졌을 때, 위에서 설명한 대로 가격을 적절히 배치하여 얻을 수 있는 최대 이익을 구하시오.

프로그램은 하나 이상의 테스트 케이스에 대해 실행된다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 100)가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 N (1 ≤ N ≤ 105)이 주어지는 한 줄로 시작하며, 다음 줄에는 공백 하나로 구분된 N개의 양의 정수가 주어진다. 이는 배정할 가격 목록이며, 각 가격은 106 이하이다.

각 테스트 케이스마다 얻을 수 있는 최대 이익을 소수점 이하 정확히 6자리로 반올림하여 한 줄에 출력한다. 결과는 1018을 넘지 않음이 보장된다.

첫 번째 테스트 케이스에서는 가격을 '2 1 3' 순서로 배정한다. 첫날에는 가지고 있는 1단위를 2달러에 팔고, 둘째 날에는 1달러씩 주고 2단위를 사며, 셋째 날에는 그 2단위를 3달러씩 받고 팔아 최종적으로 6달러의 이익을 얻는다.

두 번째 테스트 케이스에서는 하루뿐이므로, 그날 가지고 있는 1단위를 팔아야 한다.