struct node{

int premin,premax, sufmin,sufmax, p,prod;

};

node help(const vector &a,int s,int e){

node ans;

if(s==e)

{

    ans.premin=ans.sufmin=ans.sufmax=ans.p=ans.prod=ans.premax=a[s];

    return ans;

}

int m=(s+e)/2;

node l=help(a,s,m);

node r=help(a,m+1,e);

ans.p=max(l.p,max(r.p,max(l.sufmax*r.premax,l.sufmin*r.premin)));

ans.premax=max(l.premax,max(l.prod*r.premax,l.prod*r.premin));

ans.sufmax=max(r.sufmax,max(r.prod*l.sufmax,r.prod*l.sufmin));

ans.premin=min(l.premin,min(l.prod*r.premax,l.prod*r.premin));

ans.sufmin=min(r.sufmin,min(r.prod*l.sufmax,r.prod*l.sufmin));

ans.prod=l.prod*r.prod;

return ans;

}

int Solution::maxProduct(const vector &a) {

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

}