#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include "krazki.h"
#include "message.h"

typedef long long int int64;

#define MaxInstances 100

#if defined( MY_MESSAGE )
	#define tls thread_local
#else
	#define tls
#endif

tls int myid;
tls int numInstances;

tls int n;
tls int m;

#define MaxWidth ( ( int64 ) 1 << 60 )

tls int start;
tls int end;
tls int count;
tls std::vector< int64 > widths;

void init()
{
	myid = MyNodeId();
	numInstances = NumberOfNodes();

	n = PipeHeight();

	start = ( int ) ( ( int64 ) n * myid / numInstances );
	end = ( int ) ( ( int64 ) n * ( myid + 1 ) / numInstances );
	count = end - start;

	m = NumberOfDiscs();
}

void calc_widths()
{
	widths.resize( count );
	for ( int i = 0; i < count; ++i )
	{
		int64 w = HoleDiameter( start + i + 1 );
		if ( i && w > widths[ i - 1 ] )
		{
			w = widths[ i - 1 ];
		}
		widths[ i ] = w;
	}
}

void receive_top_and_send_bottom()
{
	int64 topWidth = MaxWidth;
	if ( myid )
	{
		Receive( myid - 1 );
		topWidth = GetLL( myid - 1 );
	}

	int64 bottomWidth = topWidth;
	if ( !widths.empty() && bottomWidth > widths.back() )
	{
		bottomWidth = widths.back();
	}

	if ( myid < numInstances - 1 )
	{
		PutLL( myid + 1, bottomWidth );
		Send( myid + 1 );
	}

	for ( int i = 0; i < count; ++i )
	{
		if ( widths[ i ] > topWidth )
		{
			widths[ i ] = topWidth;
		}
	}
}

struct region_t
{
	int start;
	int count_initial;
	int count_processed;

	region_t()
		: start( -1 )
		, count_initial( 0 )
		, count_processed( 0 )
	{}
};

region_t create_initial_region()
{
	region_t initialRegion;
	initialRegion.start = start - ( n - m );
	int initialRegionEnd = end - ( n - m );
	if ( initialRegion.start < 0 )
	{
		initialRegion.start = 0;
	}
	if ( initialRegionEnd < initialRegion.start )
	{
		initialRegionEnd = initialRegion.start;
	}
	initialRegion.count_initial = initialRegionEnd - initialRegion.start;

	return initialRegion;
}

void Send( const int target, const region_t& region )
{
	PutInt( target, region.start );
	PutInt( target, region.count_initial );
	PutInt( target, region.count_processed );
	Send( target );
}

void Receive( const int source, region_t& region )
{
	Receive( source );
	region.start = GetInt( source );
	region.count_initial = GetInt( source );
	region.count_processed = GetInt( source );
}

int find_height_for_disc( const int count, const int64 value )
{
	auto begin = widths.begin();
	auto end = begin + count;
	auto it = std::upper_bound( begin, end, value, [](const int64 lhs, const int64 rhs) -> bool { return lhs > rhs; } );
	if ( it != begin )
	{
		--it;
	}
	else
	{
		it = end;
	}
	return it == end ? -1 : ( int ) ( it - begin );
}

int handle_discs()
{
	int space_left;
	int needed_space;

	int stored = 0;
	int low = count;

	region_t to_process = create_initial_region();

	int numIterationsLeft = numInstances - myid;
	while ( numIterationsLeft )
	{
		// store initial

		int new_stored = 0;
		int new_low = count;

		int i = 0;
		while ( i < to_process.count_initial )
		{
			const int64 disc = DiscDiameter( m - ( to_process.start + to_process.count_initial - i ) + 1 );

			const int disc_height = find_height_for_disc( new_low, disc );
			if ( disc_height == -1 )
			{
				if ( !myid )
				{
					low = -1;
					return low;
				}

				region_t to_send;
				to_send.start = to_process.start;
				to_send.count_initial = to_process.count_initial - i;
				to_send.count_processed = to_process.count_processed + stored;
				Send( myid - 1, to_send );

				stored = new_stored;

				goto next_iteration;
			}
			else
			{
				++new_stored;
				new_low = disc_height;
				++i;
			}
		}

		// manage space left

		space_left = new_low;
		needed_space = to_process.count_processed + stored;
		if ( space_left < needed_space )
		{
			if ( !myid )
			{
				low = -1;
				return low;
			}

			const int missing_space = needed_space - space_left;

			region_t to_send;
			to_send.start = to_process.start + to_process.count_initial + space_left;
			to_send.count_initial = 0;
			to_send.count_processed = missing_space;
			Send( myid - 1, to_send );

			stored = to_process.count_initial + space_left;
			low = 0;

			goto next_iteration;
		}
		else
		{
			stored += to_process.count_initial + to_process.count_processed;
			if ( low > new_low - needed_space )
			{
				low = new_low - needed_space;
			}
		}

		// send empty region

		if ( myid )
		{
			Send( myid - 1, region_t() );
		}

next_iteration:
		// receive next region to process

		--numIterationsLeft;

		if ( numIterationsLeft )
		{
			if ( myid < numInstances - 1 )
			{
				Receive( myid + 1, to_process );
			}
		}
	}

	PutInt( 0, low == count ? -2 : start + low );
	Send( 0 );

	if ( !myid )
	{
		low = n;
		for ( int i = numInstances - 1; i >= 0; --i )
		{
			Receive( i );
			const int recv_low = GetInt( i );
			if ( recv_low != -2 && low > recv_low )
			{
				low = recv_low;
			}
		}
	}

	return low;
}

void print_result( const int low )
{
	if ( !myid )
	{
		std::cout << ( low + 1 );
	}
}

#ifdef MY_MESSAGE
int my_main( int _id )
#else
int main()
#endif
{
#ifdef MY_MESSAGE
	{
		extern thread_local int id;
		id = _id;
	}
#endif

	init();
	if ( m > n )
	{
		if ( !myid )
		{
			std::cout << 0;
		}
		return 0;
	}
	calc_widths();
	receive_top_and_send_bottom();
	const int low = handle_discs();
	print_result( low );
	return 0;
}