#include <iostream>
using namespace std;

int N;
vector<int> v(N), Tree(4*N), Lazy(4*N, 0);

void buildTree(int tidx, int lo, int hi){

	if(lo==hi){
		Tree[tidx] = v[hi];
		return;
	}

	int mid = (lo+hi)/2;

	buildTree(2*tidx+1, lo, mid);
	buildTree(2*tidx+2, mid+1, high);

	Tree[tidx] = Tree[2*tidx+1] + Tree[2*tidx+2];

}

void updateLazy(int tidx, int lo, int hi, int L, int R, int val){

	// Complete any pending updates before entering this node
	if(Lazy[tidx]!=0){
		Tree[tidx] = (hi-lo+1)*Lazy[tidx];
		if(lo!=hi){
			Lazy[2*tidx+1] += Lazy[tidx];
			Lazy[2*tidx+2] += Lazy[tidx];
		}
		Lazy[tidx] = 0;
	}
	
	// The Range which we are currently in : [lo, hi]
	// The Range we have to update for : [L, R]

	// Outside Range
	if(R<lo||L>hi) return;

	// In Range
	if(L<=lo&&hi<=R){
		// Update the Tree's value lazily, and then add update to be done for future to children.
		Tree[tidx] += (hi-lo+1)*val;
		if(lo!=hi){
			Lazy[2*tidx+1] += Lazy[tidx];
			Lazy[2*tidx+2] += Lazy[tidx];
		}
		return;
	}

	// Parital Overlap (Go to Left and Right)

	int mid = (lo+hi)/2;
	updateLazy(2*tidx+1, lo, mid, L, R, val);
	updateLazy(2*tidx+2, mid+1, hi, L, R, val);

	// Update the values once children are updated
	Tree[tidx] = Tree[2*tidx+1] + Tree[2*tidx+1];

}

int queryLazy(int tidx, int lo, int hi, int L, int R){

	// Complete any pending updates before querying this node
	if(Lazy[tidx]!=0){
		Tree[tidx] = (hi-lo+1)*Lazy[tidx];
		if(lo!=hi){
			Lazy[2*tidx+1] += Lazy[tidx];
			Lazy[2*tidx+2] += Lazy[tidx];
		}
		Lazy[tidx] = 0;
	}
	
	// The Range which we are currently in : [lo, hi]
	// The Range we have to compute the answer for : [L, R]

	// Outside Range
	if(R<lo||L>hi) return 0;

	// In Range
	if(L<=lo&&hi<=R) return Tree[idx];

	// Partial Overlap (Go to Left and Right)
	int mid = (lo+hi)/2;

	int leftans = queryLazy(2*tidx+1, lo, mid, L, R);
	int rightans = queryLazy(2*tidx+2, mid+1, hi, L, R);

	return leftans + rightans;

}