Problem Description

Snuke and Smeke decided to play a game using cards with numbers and coins.

Initially, Snuke has one card with the number $ T $ and $ K $ coins, while Smeke has $ N $ cards.
The game is divided into $ N $ rounds, and in each round, Smeke performs the following steps:

• Smeke selects one card that has not been shown to Snuke yet and shows it to Snuke. Let the number on this card be $ A $.
• Let the number on the card Snuke has be $ B $. Snuke receives $ |A-B| $ damage from Smeke.
• If Snuke has coins, he can either give one coin to Smeke and swap his card with the card with number $ A $, or do nothing without giving a coin.

In this game, Snuke wants to minimize the maximum damage he receives in each round. Snuke has figured out Smeke's strategy, and is confident that Smeke will show the card with the number $ A_i $ in the $ i $-th round, regardless of Snuke's actions.

Determine the minimum possible value of the maximum damage Snuke can receive in each round.
Note that after each round, Snuke's damage is restored by Smeke.

Input Format

The input is given from the standard input in the following format:

$ N $ $ T $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

• The first line contains the number of rounds $ N(1≦N≦100,000) $, the number on Snuke's initial card $ T(1≦T≦10^{9}) $, and the number of coins $ K(1≦K≦N) $.
• The next line contains $ N $ numbers, where the $ i $-th integer is the number $ A_{i}(1≦A_{i}≦10^{9}) $ on the card Smeke will show in the $ i $-th round.

Output Format

Output the minimum possible value of the maximum damage Snuke can receive in each round. End the line with a newline.

Sample Input and Output

Sample Input #1

5 1 1
1 2 3 4 5

Sample Output #1

2

Sample Input #2

8 9 3
11 4 5 14 19 19 8 10

Sample Output #2

6

Notes/Hints

Scoring

This problem has partial scoring. Solving this problem with the additional constraint $ N=K $ will award 20 points.

见题面 Input 部分

见题面 Output 部分