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

#include <stdio.h>
#include <algorithm>

using namespace std;

bool comp(long long a, long long b) {
	return a>b;
}
//Binary function that accepts two arguments (the first is always val,
//and the second of the type pointed by ForwardIterator), and 
// returns a value convertible to bool. 
//The value returned indicates whether the first argument is considered to go before the second.
//The function shall not modify any of its arguments.
//This can either be a function pointer or a function object.

int main()
{
	int nodes = NumberOfNodes();
	int pipeheight = PipeHeight();
	int numdiscs = NumberOfDiscs();
	
	int mynode = MyNodeId();

	if (pipeheight<numdiscs) {
		if (mynode==0)
			printf("0\n");
		return 0;
	}

	if (pipeheight<100000) {
		nodes = 1;
		if (mynode>0)
			return 0;
	}

	int low_pipe = (long long) mynode*pipeheight/nodes;
	int high_pipe = (long long) (mynode+1)*pipeheight/nodes;

	int low_disc = (long long) mynode*numdiscs/nodes;
	int high_disc = (long long) (mynode+1)*numdiscs/nodes;

	long long* pipe_buffer;
	long long* disc_buffer;

	
	long long min_pipe[nodes];
	min_pipe[mynode] = 1000000000000000015LL;
	for (int i=low_pipe+1; i<=high_pipe; ++i) {
		long long a = HoleDiameter(i);
		if (a<min_pipe[mynode]) min_pipe[mynode] = a;
	}
	long long max_disc[nodes];
	max_disc[mynode] = -1;
	for (int i=low_disc+1; i<=high_disc; ++i) {
		long long a = DiscDiameter(i);
		//pipe_buffer[i-low_pipe-1] = a;
		if (a>max_disc[mynode]) max_disc[mynode] = a;
	}

//	printf("min_pipe=%ld max_disc=%ld", min_pipe, max_disc);

	for (int i=0; i<nodes; ++i) {
		if (i!=mynode) {
			PutLL(i, min_pipe[mynode]);
			PutLL(i, max_disc[mynode]);
			Send(i);
		}
	}

	for (int i=0; i<nodes; ++i) {
		if (i!=mynode) {
			Receive(i);
			min_pipe[i] = GetLL(i);
			max_disc[i] = GetLL(i);
		}
	}

	for (int i=1; i<nodes; ++i) {
		min_pipe[i] = min(min_pipe[i], min_pipe[i-1]);
		max_disc[i] = max(max_disc[i], max_disc[i-1]);
	}	

	int pipe_to_check = -1;
	for (int i=0; i<nodes; ++i) {
		if (max_disc[mynode] > min_pipe[i]) {
			pipe_to_check = i;
			break;
		}

	}
	int stack = 1000000000; // allow enough disc elements to fall thru

	if (pipe_to_check == -1) {
		// moja czesc dysków przeleci po prostu przez cala rure; nic nie rob

	} else {
		low_pipe = (long long) pipe_to_check*pipeheight/nodes;
		high_pipe = (long long) (pipe_to_check+1)*pipeheight/nodes;

		pipe_buffer = new long long [high_pipe-low_pipe+10];

		long long cur_min;
		if (pipe_to_check>0)
			cur_min = min_pipe[pipe_to_check-1];
		else
			cur_min = 1000000000000000015LL;

		for (int i=low_pipe+1; i<=high_pipe; ++i) {
			long long a = HoleDiameter(i);
			a = min(a, cur_min);
			cur_min = a;
			pipe_buffer[i-low_pipe-1] = a;
		}

		disc_buffer = new long long [high_disc-low_disc+10];

		long long cur_max;
		if (mynode>0)
			cur_max = max_disc[mynode-1];
		else
			cur_max = 0;
		stack = 1000000000; // allow enough disc elements to fall thru
			// stack means the position of last element put there
		for (int i=low_disc+1; i<=high_disc; ++i) {
			long long a = DiscDiameter(i);
			a = max(a, cur_max);
			cur_max = a;
			disc_buffer[i-low_disc-1] = a;
			
			// where does "a" fall on pipe?
			long long * pos = upper_bound(pipe_buffer, pipe_buffer+high_pipe-low_pipe, a, comp); // first "greater" (i.e. lower)
			if (pos >= pipe_buffer+high_pipe-low_pipe) { // fell thru
				stack --; // just assume it fell on the other ones
			} else  {
				int stopped_at = (pos-pipe_buffer); // this is the index that when 0 means the item stopped at on low_pipe+1 
					// (so is on low_pipe, but stopped at low_pipe+1); max is high_pipe-low_pipe-1; min is 0
				if (low_pipe+stopped_at < stack)
					stack = low_pipe+stopped_at; // low_pipe+stopped_at - stack is now the new last element
				else
					stack --; // so if it would fall thru to further than current cursor, just assume it enlarges the stack
			}
		}
		// now we are thru; stack is the position of the "shallowest" element in the pipe
		// stack can be also theoretically bigger than "high_pipe+(high_disc-low_disc)+1". then it means all elements fell thru
	}

	if (mynode != 0) {
		PutInt(0, stack);
		Send(0);
	} else {
		int deep_stack = 1000000000;
		for (int i=nodes-1; i>=0; --i) {
			int i_stack;
			if (i>0) {
				Receive(i);
				i_stack = GetInt(i);
			} else {
				i_stack = stack;
			}
			int low_disc = (long long)i*numdiscs/nodes;
			int high_disc = (long long)(i+1)*numdiscs/nodes;
			int num_discs = high_disc - low_disc; // this many disks tried to put and shallowest ended at i_stack
			if (deep_stack-num_discs < i_stack) {
				deep_stack = deep_stack-num_discs;
			} else {
				deep_stack = i_stack;
			}
		}
		if (deep_stack > pipeheight)
			deep_stack = pipeheight - numdiscs + 1;
		else if (deep_stack < 0)
			deep_stack = 0;
		printf("%d\n", deep_stack);
	}


	return 0;
}