Min-Max Distance Game

Alice and Bob play the following game. At the start, n stones lie on one straight line on a table. The players take turns, and on a turn the player picks one of the remaining stones and removes it. The game ends when two stones are left on the line, and those two are called the result stones. Alice wants the result stones to end up as far apart as possible, and Bob wants them as close together as possible.

You are given the coordinates of the stones and the name of the player who takes the first turn. Both players play as well as they can. Compute the distance between the result stones at the end of the game.

The input is a single test case in the following format.

n f
x1 x2 ... xn

n is the number of stones, with $3 \le n \le 10^5$. f is the name of the first player, either Alice or Bob. For each i, $x_i$ is an integer that gives the distance of the i-th stone from the edge of the table, and $0 \le x_1 < x_2 < \dots < x_n \le 10^9$ holds.

Print the distance between the result stones on one line.