Example

Input

5 Alice
10 20 30 40 50


Output

30
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
inline int BobEven(int n,int *A)
{
    int mid=n/2;
    int Ans=A[mid+1]-A[1];
    for(int i=2;i<=mid;i++)
        Ans=min(Ans,A[mid+i]-A[i]);
    return Ans;
}
inline int AliceOdd(int n,int *A)
{
    int mid=n/2;
    for(int i=mid+1;i<n;i++)A[i]=A[i+1];
    return BobEven(n-1,A);
}
inline bool Check(int n,int *A,int v)
{
    int cnt=0;
    for(int i=1,j=1;i<=n;i=j+1,j=i,cnt++)
        while(j<n && A[j+1]-A[i]<v)j++;
    return (cnt>(n/2));
}
inline int AliceEven(int n,int *A)
{
    int L=1,R=A[n]-A[1];
    while(L+1<R)
    {
        int mid=(L+R)>>1;
        if(Check(n,A,mid))L=mid;
        else R=mid-1;
    }
    return Check(n,A,R)?R:L;
}
inline int BobOdd(int n,int *A)
{
    
    return min(AliceEven(n-1,A),AliceEven(n-1,A+1));
}
int n;
int A[maxn];
int main()
{
    int n,Ans;
    string S;
    cin>>n>>S;
    for(int i=1;i<=n;i++)
        cin>>A[i];
    if(S[0]=='A')Ans=n&1?AliceOdd(n,A):AliceEven(n,A);
    else Ans=n&1?BobOdd(n,A):BobEven(n,A);
    cout<<Ans<<endl;
    return 0;
}
 