//#include "teatr.h"
#include "message.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>

using ull = unsigned long long;
using namespace std;
int GetN() { return 100 * 1000 * 1000; }
int GetElement(int i) {
	return 1 + (((long long)i * 27) + i & (i % 113) + ((i % 37) ^ (i % 20)) * 3571) % 1000000;
}

struct node {
	int pos;
	int l;
	int r;
	int val;
};

bool comp(const node& a, const node& b)
{
	if (a.val == b.val)
		return a.l > b.l;
	return a.val > b.val;
}

void update(vector<ull>& BIT, int n, int idx)
{
	while (idx <= n) {
		BIT[idx]++;
		idx += idx & (-idx);
	}
}

ull query(const vector<ull>& BIT, int idx)
{
	ull ans = 0;
	while (idx) {
		ans += BIT[idx];
		idx -= idx & (-idx);
	}
	return ans;
}

const int MAX_PEOPLE = 1000000;
ull answers[MAX_PEOPLE];
 //from inclusive, to exclusive
ull solveQuery(int from, int to)
{
	const int n = to - from;
	ull subAnswer = 0;

	vector<node> nodes(2*n + 1 + MAX_PEOPLE);
	vector<ull> BIT(n + 1, 0);
	std::fill(answers, answers + MAX_PEOPLE, 0);

	for (int i = 1; i <= n; i++) 
	{
		nodes[i].val = GetElement(from + i - 1);
		nodes[i].pos = 0;
		nodes[i].l = 0;
		nodes[i].r = i;
	}

	// iterate for all queries 
	for (int i = n + 1; i <= 2*n; ++i) 
	{
		const auto valueIndex = i - n;
		nodes[i].pos = valueIndex;
		nodes[i].val = nodes[valueIndex].val;
		nodes[i].l = 1;
		nodes[i].r = valueIndex;
	}
	for (int i = 1; i <= MAX_PEOPLE; ++i)
	{
		const auto x = 2 * n + i;
		nodes[x].pos = -1;
		nodes[x].val = i;
		nodes[x].l = 1;
		nodes[x].r = n;
	}

	sort(begin(nodes) + 1, end(nodes), comp);

	for (int i = 1; i <= (int)nodes.size() - 1; ++i)
	{
		if (nodes[i].pos > 0) 
		{
			auto cnt = query(BIT, nodes[i].r) - query(BIT, nodes[i].l - 1);
			subAnswer += cnt;
		}
		else if(nodes[i].pos == 0)
		{
			update(BIT, n, nodes[i].r);
		}
		else
		{
			auto cnt = query(BIT, nodes[i].r) - query(BIT, nodes[i].l - 1);
			answers[nodes[i].val - 1] = cnt;
		}
	}

	return subAnswer;
}


/////////////////////////////
struct batch
{
	int preBatchId;
	int calcBatchId;
	int nodesCountInMySegment;
	
	batch(int pre_batch_id, int calc_batch_id, int nodes_count_in_my_segment)
		: preBatchId(pre_batch_id),
		  calcBatchId(calc_batch_id),
		  nodesCountInMySegment(nodes_count_in_my_segment)
	{
	}
};

const batch& getBatchInfo(int nodeId);

int main()
{
	const int n = GetN();
	const int myId = MyNodeId();

	auto& batchInfo = getBatchInfo(myId);
	int batchSize = n / 33;
	int from = batchInfo.preBatchId * batchSize;
	int to = batchInfo.preBatchId == 32 ? n : (from + batchSize);

	if(n <= 1e6)
	{
		if(myId == 0)
		{
			cout << solveQuery(0, n);
		}

		return 0;
	}

	auto nodeAnswer = solveQuery(from, to);
	batchSize = (n - to) / batchInfo.nodesCountInMySegment;
	from = to + batchInfo.calcBatchId * batchSize;
	to = (batchInfo.calcBatchId == batchInfo.nodesCountInMySegment - 1) ? n : (from + batchSize);

	if (batchInfo.calcBatchId != 0)
	{
		nodeAnswer = 0;
	}

	for (int i = from; i < to; ++i)
	{
		const auto nextHeight = GetElement(i) - 1;
		nodeAnswer += answers[nextHeight];
	}

	PutLL(0, nodeAnswer);
	Send(0);

	if (MyNodeId() != 0) return 0;

	nodeAnswer = 0;
	for(int i = 99; i >= 0; --i)
	{
		Receive(i);
		nodeAnswer += GetLL(i);
	}

	cout << nodeAnswer;
	return 0;
}

bool initialized = false;
batch batching[100] =
{
	// nodes 9, 96 969 700, 16 161 616
	batch(0, 0, 6),
	batch(0, 1, 6),
	batch(0, 2, 6),
	batch(0, 3, 6),
	batch(0, 4, 6),
	batch(0, 5, 6),
	// nodes 9, 93 939 400, 15 656 566
	batch(1, 0, 6),
	batch(1, 1, 6),
	batch(1, 2, 6),
	batch(1, 3, 6),
	batch(1, 4, 6),
	batch(1, 5, 6),
	// nodes 9, 90 909 100, 18 181 820
	batch(2, 0, 5),
	batch(2, 1, 5),
	batch(2, 2, 5),
	batch(2, 3, 5),
	batch(2, 4, 5),
	// nodes 8, 87 878 800, 17 575 760
	batch(3, 0, 5),
	batch(3, 1, 5),
	batch(3, 2, 5),
	batch(3, 3, 5),
	batch(3, 4, 5),
	// nodes 8, 84 848 500, 16 969 700
	batch(4, 0, 5),
	batch(4, 1, 5),
	batch(4, 2, 5),
	batch(4, 3, 5),
	batch(4, 4, 5),
	// node 7, 81 818 200, 16 363 640
	batch(5, 0, 5),
	batch(5, 1, 5),
	batch(5, 2, 5),
	batch(5, 3, 5),
	batch(5, 4, 5),
	// node 7, 78 787 900, 15 757 580
	batch(6, 0, 5),
	batch(6, 1, 5),
	batch(6, 2, 5),
	batch(6, 3, 5),
	batch(6, 4, 5),
	// node 6, 75 757 600, 15 151 520
	batch(7, 0, 5),
	batch(7, 1, 5),
	batch(7, 2, 5),
	batch(7, 3, 5),
	batch(7, 4, 5),
	// node 6, 72 727 300, 18 181 825
	batch(8, 0, 4),
	batch(8, 1, 4),
	batch(8, 2, 4),
	batch(8, 3, 4),
	// node 5, 69 697 000, 17 424 250
	batch(9, 0, 4),
	batch(9, 1, 4),
	batch(9, 2, 4),
	batch(9, 3, 4),
	// node 5, 66 666 700, 16 666 675
	batch(10, 0, 4),
	batch(10, 1, 4),
	batch(10, 2, 4),
	batch(10, 3, 4),
	// node 4, 63 636 400, 15 909 100
	batch(11, 0, 4),
	batch(11, 1, 4),
	batch(11, 2, 4),
	batch(11, 3, 4),
	// node 4, 60 606 100, 15 151 525
	batch(12, 0, 4),
	batch(12, 1, 4),
	batch(12, 2, 4),
	batch(12, 3, 4),
	// node 3, 57 575 800, 19 191 933
	batch(13, 0, 3),
	batch(13, 1, 3),
	batch(13, 2, 3),
	// node 3, 54 545 500, 18 181 833
	batch(14, 0, 3),
	batch(14, 1, 3),
	batch(14, 2, 3),
	// node 2, 51 515 200, 17 171 733
	batch(15, 0, 3),
	batch(15, 1, 3),
	batch(15, 2, 3),
	// node 2, 48 484 900, 16 161 633
	batch(16, 0, 3),
	batch(16, 1, 3),
	batch(16, 2, 3),
	// node 1, 45 454 600, 15 151 533
	batch(17, 0, 3),
	batch(17, 1, 3),
	batch(17, 2, 3),
	// node 1, 42 424 300, 14 141 433
	batch(18, 0, 3),
	batch(18, 1, 3),
	batch(18, 2, 3),
	// node 1, 39 394 000, 19 697 000
	batch(19, 0, 2),
	batch(19, 1, 2),
	// node 1, 36 363 700, 18 181 850
	batch(20, 0, 2),
	batch(20, 1, 2),
	// node 1, 33 333 400, 16 666 700
	batch(21, 0, 2),
	batch(21, 1, 2),
	// node 1, 30 303 100, 15 151 550
	batch(22, 0, 2),
	batch(22, 1, 2),
// node 1, 27 272 800, 13 636 400
	batch(23, 0, 2),
	batch(23, 1, 2),
// node 1, 24 242 500, 12 121 250
	batch(24, 0, 2),
	batch(24, 1, 2),
// node 1, 21 212 200, 21 212 200
	batch(25, 0, 1),
// node 1, 18 181 900, 18 181 900
	batch(26, 0, 1),
// node 1, 15 151 600, 15 151 600
	batch(27, 0, 1),
// node 1, 12 121 300, 12 121 300
	batch(28, 0, 1),
// node 1, 6 060 700
	batch(29, 0, 1),
// node 1, 3 030 400
	batch(30, 0, 1),
	// node 1, 0
	batch(31, 0, 1),
	batch(32, 0, 1),
};

const batch& getBatchInfo(int nodeId)
{
	return batching[nodeId];
}