map < pair <int,int> , pair<int,int> > dp;

pair <int,int> help(vector &a,int s,int e)

{

if(s>e)

    return {0,0};

if(dp.find({s,e})!=dp.end())

    return dp[{s,e}];

pair <int,int> l;

l=help(a,s+1,e);

int s1,s2;

s1=l.second+a[s];

s2=l.second-a[s];

// cout<<s1<<" "<<s2<<"\n";

if(abs(s1)<=abs(s2))

    return dp[{s,e}]={l.first,l.second+a[s]};

else

    return dp[{s,e}]={l.first+1,l.second-a[s]};

}

int Solution::solve(const vector &A) {

dp.clear();

vector <int> a;

a=A;

return help(a,0,a.size()-1).first;

}