MAXSUB - Maximum Subset of Array

no tags 

Given an array find the sum of the maximum non-empty subset of the array and also give the count of the subset. A subset of an array is a list obtained by striking off some (possibly none) numbers.

A non-empty subset implies a subset with at least 1 element in it.

Input

First line contains an integer T which is the number of integers. Following this T-cases exist.

Each case starts with a line containing an integer n which is the number of elements in the array.

The next line contains n-integers which contain the value of this subset.

Constraints

T <= 20

n <= 50,000

Each element in the array <= 1,000,000,000

Output

For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009

Example

Input:
2
5
1 -1 1 -1 1
6
-200 -100 -100 -400 -232 -450

Output:
3 1
-100 2

hide comments
Siya: 2014-11-17 14:36:36

Problem statement is not clear.

bhim: 2014-10-08 22:15:02

@.:: Pratik ::. pls clearly explain about the modulo

taking modulo of max ans is causing several wa

P_Quantum: 2014-05-29 15:30:36

nice!!

zicowa: 2014-02-02 13:08:22

i also did the same mistake

CoNtRaDiCtIoN: 2013-12-14 16:08:23

take modulus of only the no of subsets not the max of the array ... costed me so many wa

张翼德: 2012-12-16 02:39:08

easy test file :)

total 3 conditions - I forgot to put less than 0 case but still got AC :D

Last edit: 2012-12-16 04:17:28
Zhiang: 2012-06-29 18:41:37

good one... :)

Kartik A: 2012-06-15 11:58:22

Is ans for -1 -1 -1 0 0 is 0 3
and ans for 0 0 0 2 3 is 5 8 ?? Even then it's giving WA !! :'(

akb: 2012-04-08 00:18:56

beautiful...

SIDHANT SINHA: 2012-02-26 06:16:51

plz...clarify what is meant by "count of the subset"


Added by:.:: Pratik ::.
Date:2011-03-07
Time limit:0.507s-2.450s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64