#include "gap.h"

long long findGap(int T, int N)
{
	if (T==1)
	{
		long long int mn = -1, mx = 1000000000000000001;
		long long int answer[N];
		if (N % 2 == 0)
		{
			MinMax(mn, mx, &mn, &mx);
			answer[0] = mn;
			answer[N-1] = mx;
			for (long long int i = 0; i < (N-2)/2; i++)
			{
				MinMax(mn+1, mx-1, &mn, &mx);
				answer[i+1] = mn;
				answer[N-i-2] = mx;
			}
		}
		else
		{
			MinMax(mn, mx, &mn, &mx);
			answer[0] = mn;
			answer[N-1] = mx;
			for (long long int i = 0; i < (N-3)/2; i++)
			{
				MinMax(mn+1, mx-1, &mn, &mx);
				answer[i+1] = mn;
				answer[N-i-2] = mx;
			}
            
			MinMax(mn+1, mx-1, &mn, &mx);
			answer[(N-1)/2] = mn;
            
		}
        
		long long int max = -1;
		for (long long int i = 0; i < N-1; i++)
		{
			if (answer[i+1]-answer[i] > max)
			{
				max = answer[i+1]-answer[i];
			}
		}
        
		return max;
	}
	else
	{
        long long int mn = -1, mx = 1000000000000000001;
        MinMax(mn, mx, &mn, &mx);
        
        long long int bottom[N-1];
        long long int top[N-1];
        bottom[0] = mn;
        top[N-2]=mx;
        
        for (long long int i = 1; i < N-1; i++)
        {
            bottom[i] = mn+(mx-mn)*i/(N-1)+1;
            top[i-1]=bottom[i]-1;
        }

        long long int highest = -1;
        long long int currbot, currtop;
        MinMax(bottom[0], top[0], &mn, &mx);
        currtop = mx;
        for (long long int i = 1; i < N-1; i++)
        {
            MinMax(bottom[i], top[i], &mn, &mx);
            if (mn == -1)
            {
                
            }
            else
            {
                currbot=mn;
                if (highest < currbot - currtop)
                {
                    highest = currbot - currtop;
                }
                
                currtop = mx;
            }
        }
        
        return highest;
	}
}