Example

Input

5 Alice
10 20 30 40 50


Output

30
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n, N, a[100010];
char s[10];

int main(){
	scanf("%d%s", &n, s+1);
	N = (n+1)/2;
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	if (((s[1] == 'A') && (n%2 != 0)) || ((s[1] == 'B') && (n%2 == 0))){
		int ans = a[n];
		for(int i = 1; i <= n-N; i++)
			ans = min(ans,a[i+N]-a[i]);
		cout << ans << endl;
	} else {
		int l = 0, r = a[n], ans = 0;
		while (l <= r) {
			int mid = (l+r)/2, cnt = 1;
			for(int i = 1, j = 1; i <= n; i++)
				if (a[i]-a[j] > mid) cnt++, j = i;
			if (cnt > N) ans = mid, l = mid+1;
			else r = mid-1;
		}
		cout << ans+1 << endl;
	}
}