#include <vector>
using std::vector;

class SegmentTree {
private:
	vector<int> tree, lazy;
	int n;

	void pushUp(int node) {
		tree[node] = tree[node << 1] + tree[node << 1 | 1];
	}

	void pushDown(int node, int l, int r) {
		if (lazy[node]) {
			int mid = (l + r) >> 1;
			tree[node << 1] += lazy[node] * (mid - l + 1);
			lazy[node << 1] += lazy[node];
			tree[node << 1 | 1] += lazy[node] * (r - mid);
			lazy[node << 1 | 1] += lazy[node];
			lazy[node] = 0;
		}
	}

	void build(int node, int l, int r, int* a) {
		if (l == r) {
			tree[node] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(node << 1, l, mid, a);
		build(node << 1 | 1, mid + 1, r, a);
		pushUp(node);
	}

	void rangeAdd(int node, int l, int r, int ql, int qr, int val) {
		if (l >= ql && r <= qr) {
			tree[node] += val * (r - l + 1);
			lazy[node] += val;
			return;
		}
		pushDown(node, l, r);
		int mid = (l + r) >> 1;
		if (ql <= mid) rangeAdd(node << 1, l, mid, ql, qr, val);
		if (qr > mid) rangeAdd(node << 1 | 1, mid + 1, r, ql, qr, val);
		pushUp(node);
	}

	long long rangeQuery(int node, int l, int r, int ql, int qr) {
		if (l >= ql && r <= qr) return tree[node];
		pushDown(node, l, r);
		long long res = 0;
		int mid = (l + r) >> 1;
		if (ql <= mid) res += rangeQuery(node << 1, l, mid, ql, qr);
		if (qr > mid) res += rangeQuery(node << 1 | 1, mid + 1, r, ql, qr);
		return res;
	}

public:
	SegmentTree(int* a, int size) : tree(size << 2, 0), lazy(size << 2, 0), n(size) {
		build(1, 1, n, a);
	}

	void add(int l, int r, int val) {
		rangeAdd(1, 1, n, l, r, val);
	}

	long long query(int l, int r) {
		return rangeQuery(1, 1, n, l, r);
	}
};

int main() {
	return 0;
}