Given a set of N (> 1) positive integers, you are supposed to partition them into two disjoint sets A₁ and A₂ of n₁ and n₂ numbers, respectively. Let S₁ and S₂ denote the sums of all the numbers in A₁ and A₂, respectively. You are supposed to make the partition so that |n₁ - n₂| is minimized first, and then |S₁ - S₂| is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 10⁵), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 2³¹.

Output Specification:

For each case, print in a line two numbers: |n₁ - n₂| and |S₁ - S₂|, separated by exactly one space.

Sample Input 1:

10
23 8 10 99 46 2333 46 1 666 555

Sample Output 1:

0 3611

Sample Input 2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

Sample Output 2:

1 9359

题目大意：给定n个数字，把这n个数字分成2组，使得这2组的数字个数之差尽可能小的前提下，让2组数字的和之差最大。

很容易想到，2组数字个数之差不是0就是1，(n 是偶数和奇数的情况)   将较大的数放一组，较小的数一组，相减就是答案。

#include<cstdio>
#include<algorithm>
#define N 100001
int n,sum1=0,sum2=0;
int a[N];
using namespace std;
int main(){
	scanf("%d",&n);
	for(int i=0 ;i<n ;i++){
		scanf("%d",&a[i]);
	}
	
	sort(a,a+n);
	
	int x = n/2;
	for(int i=0 ;i<x ;i++){
		sum1+=a[i];
	}
	for(int i=x ;i<n ;i++){
		sum2+=a[i];
	}
	if(n%2==0)printf("0 ");
	else printf("1 ");
	printf("%d\n",sum2-sum1);
	return 0;
}