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

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

    int N;
    cin >> N;
    vector<int> w(N);

    int sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> w[i];
        sum += w[i];
    }

    // 總和為奇數 -> 不可能平分
    if (sum % 2) {
        cout << 0;
        return 0;
    }

    int target = sum / 2;

    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int x : w) {
        for (int j = target; j >= x; j--) {
            dp[j] = dp[j] || dp[j - x];
        }
    }

    cout << (dp[target] ? 1 : 0);
    return 0;
}