#include<iostream>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 110
#define T 1000
#define Inf 0x3f3f3f3f
using namespace std;

int t[N], n;
bool dp[N][2*N*T];

int main(){
    cin>>n;
    int tot = 0;
    rep(i,1,n) cin>>t[i], tot += t[i];
    dp[0][n*T] = true;
    int ans = Inf;
    rep(i,1,n) rep(j,0,2*n*T){
        if(j >= t[i]) dp[i][j] |= dp[i-1][j-t[i]];
        dp[i][j] |= dp[i-1][j+t[i]];
        if(i == n && dp[i][j]){
            ans = min(ans, (tot+abs(j-n*T))/2);
        }
    }
    cout<<ans<<endl;
    return 0;
}
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 1000000007
#define ad(a,b) a=(a+b)%mod;
ll po(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
ll gcd(ll a,ll b){
	return (b?gcd(b,a%b):a);
}
#define X 200010
ll fac[X],ivf[X];
void initfac(){
	fac[0]=1;
	for(ll i=1;i<X;i++)fac[i]=fac[i-1]*i%mod;
	for(ll i=0;i<X;i++)ivf[i]=po(fac[i],mod-2);
}
ll C(ll n,ll k){
	return fac[n]*ivf[n-k]%mod*ivf[k]%mod;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	ll n;
	string t;
	cin>>n>>t;
	ll x=10000000000;
	if(t=="0")cout<<x<<endl;
	else if(t=="1")cout<<2*x<<endl;
	else if(t=="11"||t=="10")cout<<x<<endl;
	else if(t=="01")cout<<x-1<<endl;
	else{
		ll a=-1;
		rep(i,n)if(t[i]=='0'){a=i;break;}
		bool ok=(0<=a&&a<3);
		rep(i,n){
			if(i%3==a)ok&=(t[i]=='0');
			else ok&=(t[i]=='1');
		}
		if(!ok)cout<<0<<endl;
		else{
			ll cnt=0;
			rep(i,n)cnt+=(t[i]=='0');
			if(t[n-1]=='1')cnt++;
			cout<<x-cnt+1<<endl;
		}
	}
}
