#include "device.h"
//#include <fstream.h>

//ofstream output;

int thistoohigh;
int thistoolow;
int n;
int placed = 2;
int index[1500];
int toohigh[1500];
int toolow[1500];

int m3 (int a, int b, int c)
{
	int result = Med3(a+1,b+1,c+1);
//	output << a << " " << b << " " << c << " : " << (result-1) << "\n";
	return result-1;
}

int itempos(int min, int max, int newone)
{
//	output << min << " " << max << "\n";

	if (min > n/2 && n >= 900)
	{
		return max-1;//max-1;
	}
	if (n-newone+max+10 < n/2 && n >= 900)
	{
		return 0;//min+1;
	}

	if (min > max)
		return min;
	if (min == max)
	{
		if (min == 0)
		{
			int result = m3(index[min], newone, index[placed-1]);
			if (result == index[min])
				return min;
			else
				return min+1;
		}
		else
		{
			int result = m3(index[min], newone, index[0]);
			if (result == index[min])
				return min+1;
			else
				return min;
		}
	}
	if (min == max-1)
	{
		int result = m3(index[min],newone,index[max]);
		if (result == index[min])
			return min;
		else if (result == index[max])
			return max+1;
		else
			return max;
	}

	int mid1 = (2*min+max) / 3;
	int mid2 = (min+2*max) / 3;

	int result = m3 (index[mid1], newone, index[mid2]);

	if (result == index[mid1])
		return itempos (min, mid1, newone);
	else if (result == newone)
		return itempos (mid1+1, mid2, newone);
	else
		return itempos (mid2+1, max, newone);
}

int main()
{
	int j, i;

//	output.open ("median.out");
	n = GetN();

	index[0] = 0;
	index[1] = 1;

	for (i = 2; i < n; i++)
	{
/*		output << "Starting to place i = " << i << "\n\n";
		for (j = 0; j < i; j++)
			output << index[j] << " ";
		output << "\n";*/

		int spot = itempos(0, placed-1, i);
		if (spot != -1)
		{
			for (j = i; j > spot; j--)
			{
				index[j] = index[j-1];
			}
			index[spot] = i;
			placed++;
		}
	}

	Answer(index[n/2]+1);

	return 0;
}