Example

Input

5 Alice
10 20 30 40 50


Output

30
#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> ip;
bool fs = false;

bool test(int a) {
  int id = 0;
  int t = 0;
  while (id < N) {
    int j = id;
    while (ip[j] - ip[id] < a and j < N) {
      j ++;
    }
    t += (j - id - 1);
    id = j;
  }
  int n = N - 2;
  int want = fs ? (n - n / 2) : n / 2;
  if (t <= want) return true;
  else return false;
}

bool test2(int a) {
  int z = N/2, q = N/2;
  int r = 0;
  for (int i=0; i<z; i++) {
    int t = ip[i+q] - ip[i];
    if (t < a) {
      if (r) return false;
      r = 1;
      q ++;
      t = ip[i+q] - ip[i];
      if (t < a) return false;
    }
  }
  return true;
}

int main() {
  cin >> N;
  string s;
  cin >> s;
  if (s == "Alice") fs = true;
  for (int i=0; i<N; i++) {
    int a; cin >> a;
    ip.push_back(a);
  }
  sort(ip.begin(), ip.end());
  
  if ((N&1) and !fs or !(N&1) and fs) {
    int l = 0, r = ip.back();
    while (l < r) {
      int md = (l+r+1) / 2;
      if (test(md)) {
        l = md;
      } else {
        r = md - 1;
      }
    }
    cout << l << endl;
  } else if (!(N&1)) {
    int ans = 1029384756;
    int z = N/2;
    for (int i=0; i<z; i++) {
      ans = min(ans, ip[z+i] - ip[i]);
    }
    cout << ans << endl;
  } else {
    int l = 0, r = ip.back();
    while (l < r) {
      int md = (l+r+1) / 2;
      if (test2(md)) {
        l = md;
      } else {
        r = md - 1;
      }
    }
    cout << l << endl;
  }
}