Example

Input

5 Alice
10 20 30 40 50


Output

30
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
 
 
#define SIZE 100005
 
enum Type{
    Alice,
    Bob,
};
 
enum Which{
    pre_DEL,
    pre_REST,
};
 
int N;
int table[SIZE];
bool dp[SIZE][2];
char name[10];
Type last_turn;
 
 
bool is_OK_Alice(int dist){  //辺【距離がdist未満なら張る】を全て消せるか
 
    int L,R,mid;
 
    int max_qlique = 0;
 
    for(int left = 0; left < N; left++){
        //leftを始点とした、dist未満に収まる最大の頂点数を数える
        L = left,R = N-1,mid = (L+R)/2;
        int tmp_max_qlique = 0;
 
        while(L <= R){
 
            if(table[mid]-table[left] < dist){
 
                tmp_max_qlique = mid-left+1;
                L = mid+1;
 
            }else{
 
                R = mid-1;
            }
            mid = (L+R)/2;
        }
        max_qlique = max(max_qlique,tmp_max_qlique);
    }
 
    if(max_qlique >= (N+1)/2+1){ //どうやっても辺が残るのでBob勝ち
 
        return false;
 
    }else{
 
        return true;
    }
}
 
bool is_OK_Bob(int dist){ //辺を少なくとも1本残せるか
 
    int count = 0;
 
    for(int left = 0,right = 0; right < N; right++){
 
        if(table[right]-table[left] > dist){
 
            count++;
            left = right;
        }
    }
 
    if(count >= (N+1)/2){
 
        return true;
 
    }else{ //全ての辺を消されるので不可
 
        return false;
    }
}
 
int main(){
 
    scanf("%d %s",&N,name);
 
    for(int i = 0; i < N; i++){
 
        scanf("%d",&table[i]);
    }
 
    if(name[0] == 'A'){
 
        if(N%2 == 0){
 
            last_turn = Bob;
 
        }else{
 
            last_turn = Alice;
        }
 
    }else{ //name[0] == 'B'
 
        if(N%2 == 0){
 
            last_turn = Alice;
 
        }else{
 
            last_turn = Bob;
        }
    }
 
    int L = 0,R = table[N-1],mid = (L+R)/2;
 
    int ans;
    if(last_turn == Alice){
 
        ans = L;
 
        while(L <= R){
 
            if(is_OK_Alice(mid)){
 
                ans = mid;
                L = mid+1;
 
            }else{
 
                R = mid-1;
            }
            mid = (L+R)/2;
        }
 
 
    }else{ //last_turn == Bob
 
        ans = R;
 
        while(L<=R){
 
            if(is_OK_Bob(mid)){
                ans = mid;
                L = mid+1;
 
            }else{
 
                R = mid-1; //midが小さくなるほど、辺が増えるのでBobが有利になるはず
            }
            mid = (L+R)/2;
        }
        ans++;
    }
 
    printf("%d\n",ans);
 
    return 0;
}
