#include <bits/stdc++.h>
using namespace std;

const int N = 310, M = 6e5 + 10;   //最多就是 n * a[i]
const int P = 1000000;

int a[N], f[M];  //f[i]: 有多少种加数方案能得到 i
bool g[M]; //g[i]: 0不可能，1可能
//因为对 1,000,000 取余完可能为 0，所以要多开一个 g 数组判断当前 i 是否能得到

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }


    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    f[0] = 1;
    g[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = sum; j >= a[i]; j--) {
            f[j] = (f[j] + f[j - a[i]]) % P;
            g[j] |= g[j - a[i]];
            //位运算，如果 g[j - a[i]]等于 1 那么g[j] 也等于 1
            //反之 g[j] 不变
        }
    }

    for (int i = sum / 2; i >= 0; i--) {
        if (g[i] != 0) {  // i 可以达到
            cout << (sum - i) - i << "\n";   // sum - i 是另一组数长度 
            cout << f[i] << "\n";
            break;
        }
    }

    return 0;
}