struct node{
    int l,r;
    long long sum,lazy;
}t[114514];

void update(int i)
{
    t[i].sum = t[i<<1].sum + t[i<<1|1].sum;
}

void pushdown(i)
{
    if(t[i].lazy == 0)
        return;
    t[i<<1].lazy += t[i].lazy;
    t[i<<1|1].lazy += t[i].lazy;
    t[i<<1].sum += (t[i<<1].r - t[i<<1].l+1) * t[i].lazy;
    t[i<<1|1].sum += (t[i<<1|1].r - t[i<<1|1].l+1) * t[i].lazy;
    t[i].lazy = 0;
}

void buildtree(int i,int l,int r)
{
    t[i].l = l;
    t[i].r = r;
    if(l==r)
    {
        t[i].sum = a[l];
        return;
    }

    int mid = (l+r)>>1;
    buildtree(i*2,l,mid);
    buildtree(i*2+1,mid+1,r);
    update(i);
}

void change(int i,int l,int r,int x)
{
    if(l<=t[i].l && t[i].r <= r)
    {
        t[i].sum += (t[i].r-t[i].l+1) * x;
        t[i].lazy += x;
        return;
    }
    if(t[i].l > r || t[i].r < l)
        return ;
    pushdown(i);
    change(i<<1,l,r,x);
    change(i<<1|1,l,r,x);
    update(i);
}

int query(int i,int l,int r)
{
    if(l<=t[i].l && t[i].r <= r)
        return t[i].sum;
    if(t[i].l > r || t[i].r < l)
        return 0;
    pushdown(i);
    return query(i<<1,l,r) + query(i<<1|1,l,r);
}