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

Input Specification:

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

Output Specification:

For each case, print in a line two numbers: ∣ and ∣, separated by exactly one space.

Sample Input 1:

1023 8 10 99 46 2333 46 1 666 555

Sample Output 1:

0 3611

Sample Input 2:

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

Sample Output 2:

1 9359 一句话，弱智题

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int n, s1 = 0, s2 = 0, nMin, sMin; 6 int main() 7 { 8     cin >> n; 9     vector
        
         v(n);10     for (int i = 0; i < n; ++i)11         cin >> v[i];12     sort(v.begin(), v.end());13     for (int i = 0; i < n; ++i)14     {15         if (i < n / 2)16             s1 += v[i];17         else18             s2 += v[i];19     }20     cout << n % 2 << " " << s2 - s1 << endl;21     return 0;22 }