The Return of the Reverse Flash

All submissions for this problem are available.
Eobard Thawne, "The Reverse Flash" finally figured out what time period "The Flash" is from. He also figured out a way to get back to his time by using the tachyon particles. But Flash stopped him and locked him up in the metahuman cell. But when Flash captured the Reverse Flash, he ruptured the timeline because of which Cisco Ramon is affected. Harrison Wells said that the only way to save Cisco is to restore the timeline. So, Flash has to send Reverse Flash back to the future as quickly as possible.
Flash's speed coupled with Thawne's speed will be enough to catapault Thawne through the time continuum. The only thing Flash has to do is to provide Thawne with "enough momentum" to get him past the spacetime barrier. Momentum here is proportional to the maximum sum subarray. The more the maximum sum, the more is the momentum. Enough momentum here means the maximum possible value of the maximum sum sub array. Harrison Wells found that the maximum sum subarray of any array may increase if we rearrange the elements of the array. So, to achieve enough momentum, they have to try all the possible rearrangements of the array and find the maximum possible value of the maximum sum sub array.
Now Flash needs your help. He wants you to find the maximum possible value of the maximum sum subarray. He also wants the arrangement of the array which yields that maximum value. If more than one arrangement exists, print the number of such arrangements (modulo 1000000007) and also print the lexicographically smallest arrangement.
Note:
1) For clarification on what is maximum sum subarray, please refer this link
2) Even if the number of arrangements possible is 1, print that.
Input
The first line consists of 't', the number of test cases.
Each test case has two lines, the first line being 'n', the array size and the second line consists of the array.
Constraints
1 <= t <= 1000
1 <= n <= 10^5
1 <=  a[i]  <= 10^3 (  a[i]  = Absolute value of a[i]).
Output
For each test case, print the required output. (Refer example for clarity).
Example
Input: 2 2 10 11 3 3 2 1 Output: 11 2 10 11 6 6 1 2 3
Explanation
Example case 1:
The given array is [10, 11]. There are 2 different arrangements of this array.
1) [10, 11]
2) [11, 10]
The maximum sum subarray of both the above arrangements is 11. This value corresponds to the o/p line 1.
The number of arrangements which has the maximum subarray is 2. This value corresponds to the o/p line 2.
The lexicographically smallest arrangement among the two is [10, 11] which is printed in the o/p line 3.
Example case 2:
The given array is [3, 2, 1]. There are 6 different arrangements of this array.
1) [3, 2, 1]
2) [3, 1, 2]
3) [2, 1, 3]
4) [2, 3, 1]
5) [1, 2, 3]
6) [1, 3, 2]
The maximum sum subarray of all the above arrangements is 6. This value corresponds to the o/p line 4.
The number of arrangements which has the maximum subarray is 6. This value corresponds to the o/p line 5.
The lexicographically smallest arrangement among the two is [1, 2, 3] which is printed in the o/p line 6.
Author:  lakshmi8 
Tags  lakshmi8 
Date Added:  10022016 
Time Limit:  1  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 