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
#include <tuple>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <functional>

#include "message.h"
#include "teatr.h"

using namespace std;

using ll	= long long;
using ull	= unsigned long long;
using pii	= pair<int,int>;
using pll	= pair<ll,ll>;
using vi	= vector<int>;
using vb	= vector<bool>;
using vc	= vector<char>;
using vvi	= vector<vi>;
using vpii	= vector<pii>;
using vpll	= vector<pll>;
using vll	= vector<ll>;
using vull	= vector<ull>;

#define ever (;;)
#define f first
#define s second
#define pb emplace_back
#define sz size()
#define graph vector<vertex>
#define deg(X) G[X].e.size()
#define INF 1234567890
#define INFll 2000000000000000000
#define maxe(X, Y) if((Y) > (X)) (X) = (Y)
#define mine(X, Y) if((Y) < (X)) (X) = (Y)
#define rep(i, begin, end) for(__typeof(end) i = (begin); i < (end); ++i)
#define repr(i, begin, end) for(__typeof(end) i = (begin)-1; i >= (end); --i)
#define bend(X) X.begin(), X.end()

int ID, n, NON, k, l, r;

vi T;
vi A, B;
int maxv = 0;

void in() {
	ID = MyNodeId();
	n = GetN();
	NON = NumberOfNodes();
	k = (n+NON-1)/NON;
	l = k*ID;
	r = min(n, k*(ID+1));
	T.resize(k+5);
	rep(i, l, r)
		T[i-l] = GetElement(i);
	rep(i, 0, T.sz)
		maxe(maxv, T[i]);
	++maxv;
	A.resize(maxv);
}

int main() {
	in();
	
	ll R = 0;
	
	rep(i, 0, T.sz) {
		if(T[i] == 0)
			break;
		rep(j, T[i]+1, maxv)
			R += A[j];
		++A[T[i]];
	}
	
	rep(i, ID+1, NON) {
		PutInt(i, A.sz);
		rep(j, 0, A.sz)
			PutInt(i, A[j]);
		Send(i);
	}
	rep(i, 0, ID) {
		Receive(i);
		int o = GetInt(i);
		if(o > B.sz)
			B.resize(o);
		rep(j, 0, o)
			B[j] += GetInt(i);
	}
	
	rep(i, 0, T.sz) {
		if(T[i] == 0)
			break;
		rep(j, T[i]+1, B.sz)
			R += B[j];
	}
	
	if(ID > 0) {
		PutLL(0, R);
		Send(0);
	}
	else {
		rep(i, 1, NON) {
			Receive(i);
			R += GetLL(i);
		}
		printf("%lld\n", R);
	}
	
	return 0;
}

/*
15
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
*/