// Cartesian tree: tSplit+tMerge, tInsert+tRemove, debug output
// add on segment
// calc sum on segment
// insert in any position
#include <bits/stdc++.h>
using namespace std;

using Num = long long;

mt19937 rndBits (123456);
#ifdef DEBUG
uniform_int_distribution <int> gen (0, 100);
#else
uniform_int_distribution <int> gen (0, 1000000000);
#endif

struct Node;
typedef Node * PNode;
struct Node
{
	Num value;
	Num sum; // to calc sum on segment (eagerly)
	Num toAdd; // to add on segment (lazily)
	int size;
	PNode left;
	PNode right;

	Node (Num value_)
	{
		value = value_;
		sum = value;
		toAdd = 0;
		size = 1;
		left = nullptr;
		right = nullptr;
	}

	void relax ()
	{
		if (toAdd != 0)
		{
			value += toAdd;
			if (left != nullptr)
			{
				left -> toAdd += toAdd;
				left -> recalc ();
			}
			if (right != nullptr)
			{
				right -> toAdd += toAdd;
				right -> recalc ();
			}
			toAdd = 0;
			recalc ();
		}
	}

	void recalc ()
	{
		assert (this != nullptr);

		size = 1;
		if (left != nullptr) size += left -> size;
		if (right != nullptr) size += right -> size;

		sum = value + toAdd * size;
		if (left != nullptr) sum += left -> sum;
		if (right != nullptr) sum += right -> sum;
	}
};

int tSize (PNode const t)
{
	return (t == nullptr) ? 0 : t -> size;
}

pair <PNode, PNode> tSplitSize (PNode t, int k)
{ // res.first: first k elements;   res.second: all other elements
	if (t == nullptr) return {nullptr, nullptr};
	t -> relax ();
	auto leftSize = tSize (t -> left);
	if (leftSize >= k) // k <= leftSize
	{
		auto temp = tSplitSize (t -> left, k);
		t -> left = temp.second;
		t -> recalc ();
		return {temp.first, t};
	}
	else // k > leftSize    <=>    k >= leftSize + 1
	{
		auto temp = tSplitSize (t -> right, k - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	l -> relax ();
	r -> relax ();
	if (uniform_int_distribution <int> (0, l -> size + r -> size)
	    (rndBits) < l -> size)
	{
		l -> right = tMerge (l -> right, r);
		l -> recalc ();
		return l;
	}
	else
	{
		r -> left = tMerge (l, r -> left);
		r -> recalc ();
		return r;
	}
}

PNode tInsertAt (PNode t, Num value, int pos)
{ // 0[...)len  ->  0[...)pos, value, pos[...)len
	auto temp = tSplitSize (t, pos);
	auto v = new Node (value);
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

void recurDelete (PNode t)
{
	if (t == nullptr) return;
	recurDelete (t -> left);
	recurDelete (t -> right);
	delete t;
}

PNode tRemoveAt (PNode t, int pos)
{ // 0[...)len  ->  0[...)pos, pos+1[...)len
	auto one = tSplitSize (t, pos); // 0[...)pos, pos[...)len
	auto two = tSplitSize (one.second, 1); // pos[...)pos+1,  pos+1[...)len
	recurDelete (two.first); // can omit this
	return tMerge (one.first, two.second);
}

Num tElementAt (PNode const t, int pos)
{
	if (t == nullptr) assert (false);
	auto leftSize = tSize (t -> left);
	if (pos == leftSize) return t -> value;
	if (pos < leftSize) return tElementAt (t -> left, pos);
	return tElementAt (t -> right, pos - leftSize - 1);
}

void tOutput (PNode t)
{
	if (t == nullptr) return;
	t -> relax ();
//	cout << "(";
	tOutput (t -> left);
//	cout << t -> value << " ";
	cout << t -> value << "|" << t -> sum << " ";
	tOutput (t -> right);
//	cout << ")";
}

void tOutputAll (PNode t)
{
#ifdef DEBUG
	tOutput (t);
	cout << endl;
#else
	assert (t == NULL || t != NULL);
#endif
}

PNode addOnSegment (PNode t, int lo, int hi, Num toAdd)
{ // every element of array[lo..hi) += toAdd
	auto one = tSplitSize (t, hi);  // [0..hi), [hi..end)
	auto two = tSplitSize (one.first, lo);  // [0..lo), [lo..hi)
	// segments:   two.first   *two.second*   one.second
	two.second -> toAdd += toAdd;
	two.second -> sum += toAdd * (hi - lo);
	one.first = tMerge (two.first, two.second);
	return tMerge (one.first, one.second);
}

pair <Num, PNode> sumOnSegment (PNode t, int lo, int hi)
{ // sum of every element of array[lo..hi)
	auto one = tSplitSize (t, hi);  // [0..hi), [hi..end)
	auto two = tSplitSize (one.first, lo);  // [0..lo), [lo..hi)
	// segments:   two.first   *two.second*   one.second
	auto res = two.second -> sum;
	one.first = tMerge (two.first, two.second);
	return {res, tMerge (one.first, one.second)};
}

int main ()
{
	PNode root = nullptr;
	int const limit = 10;
	for (int i = 0; i < limit; i++)
	{
		root = tInsertAt (root, i, i);
		tOutputAll (root);
	}
	for (int i = 0; i <= limit / 2; i++)
	{
		root = addOnSegment (root, i, i + limit / 2, i + 1);
/*
		auto temp = sumOnSegment (root, 0, limit);
		cout << temp.first << endl;
		root = temp.second;
*/
//		tOutputAll (root);
	}
	auto temp = sumOnSegment (root, 0, limit);
	cout << temp.first << endl;
	root = temp.second;
	tOutputAll (root);
	return 0;
}