struct node{
    int left,right;
    long long sum,weight;
}tree[upper_bound];

int A[upper_bound];//upper_bound_n

void build(int i,int a,int b){
    //tree[i].left tree[i].right为节点i的左右边界
    if(a != b){
        tree[i].left = a;tree[i].right= b;
        build(i<<1,a,(a+b)>>1);//递归构造左子树
        build((i<<1)+1,((a+b)>>1)+1,b);//递归构造右子树
        tree[i].sum  = tree[i<<1].sum + tree[(i<<1)+1].sum;//回溯 左右子树的和等于父节点
    }
    else{
        tree[i].left = tree[i].right = a;
        tree[i].sum  = A[a];
    }
    tree[i].weight = 0;
}

int add(int i,int a,int b,int v){
    if(tree[i].left == a && tree[i].right == b){
        //恰好是这个区间
        //如果遍历到叶子节点再加的话会超时的
        tree[i].weight += v;//将这个值保存而不是直接累加
        return 1;
    }
    else{
        //不是该区间但是属于该区间
        tree[i].sum += v*(b - a + 1);
        //之前写成 tree[i].sum += (tree[i].right - tree[i].left + 1)*v WA了好多次
    }
    int mid = (tree[i].left+tree[i].right) >> 1;
    if(a <= mid && b > mid){
        add(i<<1,a,mid,v);
        add((i<<1)+1,mid+1,b,v);
    }
    else{
        add((i<<1)+(b<=mid?0:1),a,b,v);
    }
    return 1;
}

long long query(int i,int a,int b){
    int mid = (tree[i].left+tree[i].right) >> 1;
    if(tree[i].left == a && tree[i].right == b){
        return tree[i].sum + (tree[i].right - tree[i].left + 1)*tree[i].weight;
    }
    else if(tree[i].weight != 0){
        tree[i].sum            += (tree[i].right - tree[i].left + 1)*tree[i].weight;//首先更新自己
        tree[i<<1].weight      += tree[i].weight;//然后传递给左右子树
        tree[(i<<1)+1].weight  += tree[i].weight;
        tree[i].weight         = 0;//自身清零

    }
    if(a <= mid && b > mid){
        return query(i<<1,a,mid) + query((i<<1)+1,mid+1,b);
    }
    return query((i<<1) + (b<=mid?0:1),a,b);
}