#include<cstdio>

#define N 100010

typedef long long ll;

int n,m,cnt,lim,i,op,x,y,pos[N],st[N],en[N],R[N],q[N];ll v[N],ts[N],td[N];

inline int read(){

  char c;bool f=0;int a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

  return a;

}

inline double cross(int x,int y){return(double)(v[x]-v[y])/(double)(y-x);}

inline void build(int x){

  int i,L=st[x],t=L;

  q[t]=t;

  for(i=t+1;i<=en[x];q[++t]=i++)while(t>L&&cross(i,q[t])<=cross(q[t],q[t-1]))t--;

  R[x]=t;

}

inline void change(int x,int y,ll s,ll d){

  if(pos[x]==pos[y]){

    for(int i=x;i<=y;i++)v[i]+=s+d*i;

    build(pos[x]);

    return;

  }

  for(int i=pos[x]+1;i<pos[y];i++)ts[i]+=s,td[i]+=d;

  for(int i=en[pos[x]];i>=x;i--)v[i]+=s+d*i;

  build(pos[x]);

  for(int i=st[pos[y]];i<=y;i++)v[i]+=s+d*i;

  build(pos[y]);

}

inline void modify(int x,int y,ll z){

  change(x,y,z*(1-x),z);

  if(y<n)change(y+1,n,z*(y-x+1),0);

}

inline void up(ll&a,ll b){if(a<b)a=b;}

inline ll ask(int x){

  int t=st[x],l=t+1,r=R[x],mid;

  while(l<=r){

    mid=(l+r)>>1;

    if(cross(q[mid-1],q[mid])<td[x])l=(t=mid)+1;else r=mid-1;

  }

  return td[x]*q[t]+ts[x]+v[q[t]];

}

inline ll query(int x,int y){

  ll t=-(1LL<<62);

  if(pos[x]==pos[y]){

    for(int i=x;i<=y;i++)up(t,td[pos[i]]*i+ts[pos[i]]+v[i]);

    return t;

  }

  for(int i=pos[x]+1;i<pos[y];i++)up(t,ask(i));

  for(int i=en[pos[x]];i>=x;i--)up(t,td[pos[i]]*i+ts[pos[i]]+v[i]);

  for(int i=st[pos[y]];i<=y;i++)up(t,td[pos[i]]*i+ts[pos[i]]+v[i]);

  return t;

}

int main(){

  n=read();

  for(i=1;i<=n;i++)v[i]=v[i-1]+read();

  while(lim*lim*8<n)lim++;

  for(i=1;i<=n;i++)pos[i]=(i-1)/lim+1;

  cnt=pos[n];

  for(i=1;i<=n;i++)en[pos[i]]=i;

  for(i=n;i;i--)st[pos[i]]=i;

  for(i=1;i<=cnt;i++)build(i);

  m=read();

  while(m--){

    op=read(),x=read(),y=read();

    if(!op)modify(x,y,read());else printf("%lld\n",query(x,y));

  }

  return 0;

}