#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#include "message.h"
#include "krazki.h"

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

LL *kra, *rury;

int main()
{
	int m = NumberOfDiscs();
	int n = PipeHeight();

	int ileI = NumberOfNodes();
	int id = MyNodeId();

	if (m > n)
	{
		if (!id)
			printf("0\n");

		return 0;
	}

	if (n < ileI)
		ileI = n;

	if (id >= ileI)
		return 0;

	// wylicz ile elementow bede przetwarzal
	int ile = n / ileI;
	int beg = id*ile;

	if (id == ileI - 1)
	{
		ile += n % ileI;
	}

	rury = new LL[ile + 1];

	int ilem, begm;

	//przygotuj rury
	REP(i, ile)
	{
		rury[i] = HoleDiameter(i + beg + 1);
		if (i && rury[i - 1] < rury[i])
			rury[i] = rury[i - 1];
	}

	// wez od poprzedniego minimalna wartosc na koncu jego rur
	LL prev = rury[ile - 1];
	if (id)
	{
		Receive(id - 1);
		prev = GetLL(id - 1);
	}

	// przeslij minimalna wartosc kolejnemu
	if (id < ileI - 1)
	{
		PutLL(id + 1, min(prev, rury[ile - 1]));
		Send(id + 1);
	}

	// musisz poprawic swoje rury
	if (id)
	{
		REP(i, ile)
		{
			if (rury[i] <= prev)
				break;
			rury[i] = prev;
		}
	}

	// wez od nastepnego info ile krazkow wzietych juz zostalo
	int sufm = 0;
	if (id < ileI - 1)
	{
		Receive(id + 1);
		sufm = GetInt(id + 1);
	}

	// zobaczy ile jeszcze mozemy wziac
	if (m - sufm < ile)
	{
		// bierz wszystko od poczatku
		ilem = m - sufm;
		sufm = m;
	}
	else
	{
		// wez tyle ile masz rur
		ilem = ile;
		sufm += ile;
	}

	begm = m - sufm;
	kra = new LL[ilem + 1];

	// przekaz poprzedniemu info ile bedziesz brac krazkow
	if (id)
	{
		PutInt(id - 1, sufm);
		Send(id - 1);
	}

	/*printf("inst: %d ileRur: %d poczatek: %d ileKrazkow: %d poczatek: %d\n", id, ile, beg, ilem, begm);
	fflush(stdout);*/

	// przygotuj swoje krazki
	kra[ilem] = 0;
	FORD(i, ilem, 0)
	{
		kra[i] = DiscDiameter(m - i - begm);
		kra[i] = max(kra[i], kra[i + 1]);
	}

	// zapytaj sie nastepnego o jego topowy krazek
	LL next = kra[ilem - 1];
	if (id < ileI - 1)
	{
		Receive(id + 1);
		next = GetLL(id + 1);
	}

	// przeslij max wartosc poprzednikowi
	if (id)
	{
		PutLL(id - 1, max(next, kra[0]));
		Send(id - 1);
	}

	// popraw swoje krazki
	if (id < ileI - 1)
	{
		FORD(i, ilem, 0)
		{
			if (kra[i] >= next)
				break;
			kra[i] = next;
		}
	}

	/*printf("inst: %d\n", id);
	fflush(stdout);
	printf("kra: ");
	fflush(stdout);
	REP(i, ilem)
	{
		printf("%d ", kra[i]);
		fflush(stdout);
	}
	printf("\n");
	fflush(stdout);
	printf("rury: ");
	fflush(stdout);
	REP(i, ile)
	{
		printf("%d ", rury[i]);
		fflush(stdout);
	}
	printf("\n");
	fflush(stdout);*/

	// jedz algorytm i wylicz ile Ci sie nie zmiesci
	int first = ile, last = ile, lastm = ilem - 1, cntR = ile - 1;

	// jesli jest sens cokolwiek robic, to odpal algo, jak nie, to pusc dalej
	if (kra[lastm] <= rury[0])
	{
		while (lastm >= 0 && cntR >= 0)
		{
			while (cntR >= 0 && rury[cntR] < kra[lastm])
				cntR--;
			if (cntR >= 0)
			{
				if (last == ile)
					last = cntR;
				first = cntR;
				lastm--;
				cntR--;
			}
		}
	}

	bool sent = 0;

	int ileNdm = lastm + 1;
	// mamy wolne miejsce i nadmiar u siebie wyliczone, wez nadmiar od nastepnego
	if (id < ileI - 1)
	{
		Receive(id + 1);
		int ileNdmN = GetInt(id + 1);

		// przetworz nadmiar

		int ileZrobil = ilem - lastm - 1;
		/*printf("id: %d zrobil: %d\n", id, ileZrobil);
		fflush(stdout);*/

		int ileDziur = last - ileZrobil + 1;

		// zmiescimy wszystko w dziurach - co oznacza, ze nie bedzie  dodatkowego nadmiaru
		// to bedzie dzialac, pod warunkiem, ze udalo nam sie min 1 element wrzucic
		// jesli sie nie udalo, to nawet wartosc ileDziur jest za duza o 1
		if (ileZrobil > 0 && ileNdmN <= ileDziur && id)
		{
			// wyslij aktualny nadmiar
			PutInt(id - 1, ileNdm);
			Send(id - 1);
			sent = 1;
		}

		// wylicz pozycje first dokladnie, jadac algorytm jeszcze raz
		ileNdmN += ileZrobil;

		//printf("id: %d, ileNdmN: %d\n", id, ileNdmN);
		//fflush(stdout);

		LL *pomKra;

		pomKra = new LL[ileNdmN + 1];
		pomKra[ileNdmN] = 0;

		REP(i, ileNdmN)
			pomKra[i] = DiscDiameter(m - begm - ilem + ileZrobil - i);
		FORD(i, ileNdmN, 0)
			pomKra[i] = max(pomKra[i], pomKra[i + 1]);

		last = first = ile;
		cntR = ile - 1;
		lastm = ileNdmN - 1;
		// jesli jest sens cokolwiek robic, to odpal algo, jak nie, to pusc dalej
		if (pomKra[lastm] <= rury[0])
		{
			while (lastm >= 0 && cntR >= 0)
			{
				while (cntR >= 0 && rury[cntR] < pomKra[lastm])
					cntR--;
				if (cntR >= 0)
				{
					if (last == ile)
						last = cntR;
					first = cntR;
					lastm--;
					cntR--;
				}
			}
		}

		ileNdm += lastm + 1;

		delete[] pomKra;

		/*printf("id: %d ndm: %d\n", id, ileNdm);
		fflush(stdout);*/
		
	} //if id < ileI-1

	// wyslij swoj nadmiar poprzednikowi
	if (id && !sent)
	{
		PutInt(id - 1, ileNdm);
		Send(id - 1);
	}

	// ustal polozenie pierwszego krazka
	int posNext = last;
	if (id < ileI - 1)
	{
		Receive(id + 1);
		posNext = GetInt(id + 1);
	}

	//printf("id: %d first: %d posNext: %d\n", id, first, posNext);

	if (first == ile)	//nic nie ulozylismy
		first = posNext;		// przekaz pozycje z nastepnika
	else
		first += beg;	//przekaz pozycje, gdzie my cos ulozylismy

	if (id)
	{
		PutInt(id - 1, first);
		Send(id - 1);
	}
	else
	{
		// wypisz wynik
		if (ileNdm > 0)
		{
			printf("0\n");
		}
		else
		{
			printf("%d\n", first + 1);
		}
	}

	delete[] kra, delete[] rury;

	return 0;
}