配点 : $400$ 点

問題文

$a\leq b$ を満たす正整数 $a, b$ および，正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます．

あなたはこの数列に対して，以下の操作を何度でも行うことができます（$0$ 回でもよいです）：

• 相異なる添字 $i, j$ ($1\leq i, j \leq N$) を選ぶ．$A_i$ に $a$ を加え，$A_j$ から $b$ を引く．

操作後の $\min(A_1, A_2, \ldots, A_N)$ としてありうる最大値を求めてください．

制約

• $2\leq N\leq 3\times 10^5$
• $1\leq a\leq b\leq 10^9$
• $1\leq A_i\leq 10^{9}$

入力

入力は以下の形式で標準入力から与えられます．

$N$ $a$ $b$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

操作後の $\min(A_1, A_2, \ldots, A_N)$ としてありうる最大値を出力してください．

3 2 2
1 5 9

5

例えば次のように操作を行うことで， $\min(A_1, A_2, A_3) = 5$ を達成できます．

• $i = 1, j = 3$ として操作を行う．$A$ は $(3, 5, 7)$ に変化する．
• $i = 1, j = 3$ として操作を行う．$A$ は $(5, 5, 5)$ に変化する．

3 2 3
11 1 2

3

例えば次のように操作を行うことで， $\min(A_1, A_2, A_3) = 3$ を達成できます．

• $i = 1, j = 3$ として操作を行う．$A$ は $(13, 1, -1)$ に変化する．
• $i = 2, j = 1$ として操作を行う．$A$ は $(10, 3, -1)$ に変化する．
• $i = 3, j = 1$ として操作を行う．$A$ は $(7, 3, 1)$ に変化する．
• $i = 3, j = 1$ として操作を行う．$A$ は $(4, 3, 3)$ に変化する．

3 1 100
8 5 6

5

一度も操作を行わないことにより， $\min(A_1, A_2, A_3) = 5$ を達成できます．

6 123 321
10 100 1000 10000 100000 1000000

90688