#include <bits/stdc++.h>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define int long long

bool can[(int) 1e5 + 5] = {false};

int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x: a) cin >> x;

    int s = accumulate(all(a), 0);

    can[0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = (int)1e5; j >= 0; --j) {
            if (j + a[i] <= (int)1e5) 
                can[j + a[i]] |= can[j];
        }
    }

    int mn = 1e18;
    for (int j = 0; j <= (int)1e5; ++j) {
        if (can[j]) 
            mn = min(mn, max(j, s - j));
    } 
    cout << mn;
}
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
const int mod=1e9+7;
int n,i,a[100005],s=1;
int main(){
	cin>>n;
	rep(i,n)cin>>a[i];
	sort(a+1,a+n+1);
	rep(i,n){
		s=1ll*s*(a[i]-a[i-1]+1)%mod;
	}
	cout<<s<<endl; 
	return 0;
}