#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define endl "\n"
#define float long double
#define int long long int
#define f(i, a, b) for(int i=a; i<b; i++)
#define fb(i, a, b) for(int i=a; i>=b; i--)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define LB lower_bound
#define UB upper_bound
#define g(t, n) get<n>(t)
#define fp(x, y) fixed<<setprecision(y)<<x
#define PI 3.141592653589793238462643383279502884
using namespace std;

const int M = (int)2e5+5;
const int mod = (int)1e9+7;

int cnt[M], p[M];

void solve()
{
    int n, j = 0;
    cin>>n;
    f(i, 0, n)
    {
    	cin>>p[i];
    	cnt[p[i]]++;
    	while(cnt[j]) j++;
    	cout<<j<<endl;
    }
}

int32_t main()
{
    IOS
    int t = 1;
    // cin>>t;
    f(tno, 1, t+1)
    {
        // cout<<"Case #"<<tno<<": ";
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class T = ll> using V = vector<T>;
#define loop(n) while(n--)
#define rep(i,n) for(int i=0; i<(n);++i)
#define repp(i, l, r) for(int i = (l); i < (r); ++i)
#define all(v) (v).begin(), (v).end()
#define LL(n) int n;cin >> n

int main()
{
    LL(n);
    V<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    ll MIN = accumulate(all(a), 0);
    if(MIN%2==1) MIN = MIN/2 + 1;
    else MIN = MIN/2;
    int K = 100000;
    vector<vector<bool>> dp(n + 1, vector<bool>(K, false));
    // 初期化
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    // 更新
    for (int i = 0; i < n; i++) {
        for (int k = 0; k <= K; k++) {
            if (k - a[i] >= 0) dp[i + 1][k] = dp[i + 1][k] | dp[i][k - a[i]];
            dp[i + 1][k] = dp[i + 1][k] | dp[i][k];
        }
    }

    rep(i, 100000){
        if(dp[n][i+MIN]) {
            cout << i+MIN << endl;
            break;
        }
    }

    return 0;
}
