Example

Input

5 Alice
10 20 30 40 50


Output

30
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <bitset>
using namespace std;

const int MAXN = 100005;
int stones[MAXN], del[MAXN], n;
bool aliceFirst;

// even number of stones, and bob first, will Alice win?
bool check1(int length) {
  vector<int> arr;
  for (int i = 1; i <= n; i++) {
    if (del[i] == length) continue;
    arr.push_back(stones[i]);
  }
  int sz = int(arr.size()) >> 1;
  for (int i = 0, j = i + sz; j < arr.size(); i++, j++) {
    // puts("Fuck 1!");
    if (arr[j] - arr[i] < length) return false;
  }
  return true;
}

// even number of stones, and alice first, will Bob win?
bool check2(int length) {
  vector<int> arr;
  for (int i = 1; i <= n; i++) {
    if (del[i] == length) continue;
    arr.push_back(stones[i]);
  }
  int sz = int(arr.size()) >> 1, ans = 0, start = 0, end = 0;
  int lim = int(arr.size());
  while (start < lim) {
    // printf("Size is %d\n", lim);
    // printf("Start is %d\n", start);
    end = start + 1;
    ans++;
    while (end < lim && arr[end] - arr[start] < length) end++;
    // printf("End is %d\n", end);
    // printf("Fuck 2!\n");
    start = end;
  }
  return ans <= sz;
}

// check whether Alice will win
bool check(int length) {
  if (!(n & 1) && !aliceFirst)
    return check1(length);
  else if ((n & 1) && aliceFirst) {
    del[(n + 1) / 2] = length;
    return check1(length);
  } else if (!(n & 1) && aliceFirst) {
    return !check2(length);
  } else {
    int lneed[MAXN] = {}, rneed[MAXN] = {};
    int lfa[MAXN] = {}, rfa[MAXN] = {};
    lfa[0] = 1;
    lneed[0] = 1;
    for (int i = 1; i <= n; i++) {
      lfa[i] = lfa[i - 1];
      lneed[i] = lneed[i - 1];
      if (abs(stones[i] - stones[lfa[i]]) >= length) {
        lfa[i] = i;
        lneed[i]++;
      }
    }
    rfa[n + 1] = n;
    rneed[n + 1] = 1;
    for (int i = n; i >= 1; i--) {
      rfa[i] = rfa[i + 1];
      rneed[i] = rneed[i + 1];
      if (abs(stones[i] - stones[rfa[i]]) >= length) {
        rfa[i] = i;
        rneed[i]++;
      }
    }
    
    // printf("Now Length is %d\n", length);
    // for(int i=1;i<=n;i++) printf("%d ", lneed[i]); puts("");
    // for(int i=1;i<=n;i++) printf("%d ", lfa[i]); puts("");
    // for(int i=1;i<=n;i++) printf("%d ", rneed[i]); puts("");
    // for(int i=1;i<=n;i++) printf("%d ", rfa[i]); puts("");
    
    for (int i = 1; i <= n; i++) {
      del[i - 1] = length - 1;
      del[i] = length;
      int pos = i + 1;
      int fa = lfa[i - 1];
      while (pos <= n && abs(stones[pos] - stones[fa]) < length) pos++;
      int want = lneed[i - 1] + ((pos <= n) ? (lneed[n] - lneed[pos - 1]) : 0);
      // printf("want %d segments\n", want);
      // int want = lneed[i-1] + rneed[i+1];
      // if(abs(stones[lfa[i-1]] - stones[rfa[i+1]]) <= length) want--;
      if (want <= (n >> 1)) return false;
    }
    
    return true;
  }
}

int main() {
  char ss[10];
  while (~scanf("%d%s", &n, ss)) {
    memset(del, false, sizeof(del));
    if (strcmp(ss, "Alice") == 0)
      aliceFirst = true;
    else
      aliceFirst = false;
    for (int i = 1; i <= n; i++) scanf("%d", &stones[i]);
    int ans = -1, left = 1, right = stones[n] - stones[1];
    while (left <= right) {
      int mid = (left + right) >> 1;
      // printf("MID is %d\n", mid);
      if (check(mid)) {
        ans = mid;
        left = mid + 1;
      } else
        right = mid - 1;
    }
    printf("%d\n", ans);
  }
  return 0;
}