1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include "message.h"
#include "teatr.h"
//using namespace __gnu_pbds;
using namespace std;
#define ff first
#define dd second
#define mp make_pair
typedef long long lld;
#define pb emplace_back
#define sz size()
#define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i)
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define rpt(S,it) for(auto it=S.begin();it!=S.end();++it)
//#define mod (lld)(1e9+7)
#define scanf(...) scanf(__VA_ARGS__)?:0
#define P first
#define S second
#ifdef __WIN32__
#define gcx getchar
#elif __linux__
#define gcx getchar_unlocked
#endif
#define piii pair<pii,pii>
//template<typename T>
#define T lld
inline void scan(T *i)
{
	register T t=0;
	register char z='a';
	register bool neg=0;
	while(z<'0' || z>'9'){if(z=='-')neg^=1;
	z=gcx();}
	while(z>='0' && z<='9')
	{
		t=(t<<3ll)+(t<<1ll)+z-'0';
		z=gcx();
	}
	if(neg)t=~(t-1);
	*i=t;
}

int tree[1048576],c[1048576],ile[1048576];

	int p,k;
	lld wyn=0;
	int maxn=0;

void upd(int x, int val)
{
	while(x)tree[x]+=val,x-=(x&(-x));
}

int get(int x)
{
	int ret=0;
	while(x<1048576)
	ret+=tree[x],x+=(x&(-x));
	return ret;
}

bool sol(int a, int ktory)
{
	p=(1000000)*ktory;
	k=(1000000)*(ktory+1);
	k=min(k,a);
	//cout<<p<<" "<<k<<" "<<ktory<<endl;
	if(p>=a){PutLL(0,0);Send(0);return 1;}
	
	For(i,p,k)
	c[i-p]=GetElement(i);
	For(i,0,k-p){
		maxn=max(maxn,c[i]);
		upd(c[i],1);
		wyn+=get(c[i]+1);
		++ile[c[i]];
	}
	//cout<<wyn<<endl;
	for(int i=maxn-1;i;--i)ile[i]+=ile[i+1];
	//For(i,0,maxn+1)cout<<i<<" "<<ile[i]<<endl;
	For(i,k,a)
	wyn+=ile[GetElement(i)+1];
	//cout<<wyn<<endl;
	return 0;
}

void push(int a, int ktory)
{
	PutLL(0,wyn);
	Send(0);
	//cout<<ktory<<" OK "<<endl;
}

void play(int a, int ktory)
{
	//--ktory;
	Receive(ktory);
	wyn+=GetLL(ktory);
}


int main()
{
	int thiss=MyNodeId();
	int a=GetN();
	if(sol(a,thiss))return 0;
	//cout<<wyn<<endl;
	if(thiss)
	push(a,thiss);
	//if(!thiss)For(i,0,maxn+1)cout<<ile[i]<<" "<<i<<endl;
	
	if(!thiss)
	For(i,1,NumberOfNodes())
	play(a,i);
	//if(k==a)
	if(!thiss)
	printf("%lld",wyn);
	return 0;
	
}