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

首先要保证n1和n2相差最小无非是相差0或者1，也就是n是偶数或者是奇数，然后再保证s1和s2相差最大，排个序，从中间分开即可。
代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int s[];

int n;

int main()

{

    cin>>n;

    for(int i = ;i < n;i ++)

    {

        cin>>s[i];

    }

    sort(s,s + n);

    int sum = ;

    for(int i = ;i < n / ;i ++)

        sum += s[n - i - ] - s[i];

    if(n % )

    {

        cout<<<<' '<<sum + s[n / ];

    }

    else cout<<<<' '<<sum;

}