Example

Input

5 Alice
10 20 30 40 50


Output

30
#include <iostream>
#include <cstdio>
using namespace std;

const int MaxN = (int)1e5+7;

int n,a[MaxN],ans; char str[10];


int main()
{
	//freopen("K.in","r",stdin);
	//freopen("K.out","w",stdout);

	int i,j,le,ri,mi,cnt;

	scanf("%d",&n);
	scanf("%s",str+1);
	for(i=1;i<=n;i++)
		scanf("%d",a+i);

	if((str[1]=='A' && (n&1)) || (str[1]=='B' && (!(n&1))))
	{
		ans = 1<<30; j =(n+1)/2;
		for(i=1;i+j<=n;i++)
			ans = min(ans , a[i+j]-a[i]);
	}
	else
	{
		le = 0, ri = a[n];
		while(le<=ri)
		{
			mi = (le+ri)>>1;
			cnt = 1;
			for(i=j=1;i<=n;i++)
				if(a[i]-a[j]>mi) cnt++,j=i;
			//printf("%d %d\n",mi,cnt);
			if(cnt>(n+1)/2) le = mi+1;
			else ri = mi-1;
		}
		ans = le;
	}

	printf("%d\n",ans);

	return 0;
}