11757번 - Min-Max Distance Game 다국어

Alice and Bob are playing the following game. Initially, n stones are placed in a straight line on a table. Alice and Bob take turns alternately. In each turn, the player picks one of the stones and removes it. The game continues until the number of stones on the straight line becomes two. The two stones are called result stones. Alice’s objective is to make the result stones as distant as possible, while Bob’s is to make them closer.

You are given the coordinates of the stones and the player’s name who takes the first turn. Assuming that both Alice and Bob do their best, compute and output the distance between the result stones at the end of the game.

The input consists of a single test case with the following format.

n f
x1 x2 · · · xn

n is the number of stones (3 ≤ n ≤ 10⁵). f is the name of the first player, either Alice or Bob. For each i, x_i is an integer that represents the distance of the i-th stone from the edge of the table. It is guaranteed that 0 ≤ x₁ < x₂ < · · · < x_n ≤ 10⁹ holds.

Output the distance between the result stones in one line.