Подорож у тумані#11141

Подорож у тумані

2 секунди

512 мегабайтів

Дуже складна

Юлія та Джейн — дві подруги, які живуть на протилежних кінцях довгої вузької вулиці довжиною $L$ .

Сьогодні Юлії потрібно зустрітися з Джейн і повернутися додому якомога швидше.

Джейн має список швидкостей $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n. У момент часу $0$ Джейн вибирає ціле число $i$ від $1$ до $n$ рівноймовірно і починає рухатися до Юлії з постійною швидкістю $v_{i}$ v_i.

Юлія не має таких обмежень у своїх рухах. Починаючи з моменту часу $0$ , Юлія може вільно рухатися вздовж вулиці в будь-якому напрямку з будь-якою швидкістю, що не перевищує $V$ . Зокрема, Юлія може залишатися на місці стільки, скільки захоче, рухатися зі швидкостями меншими за $V$ і змінювати свою швидкість у будь-який момент.

На вулиці туман. Тому Юлія та Джейн не можуть бачити одна одну, якщо вони не знаходяться в одній точці вулиці. Також зауважте, що Юлія не знає швидкість Джейн, але вона знає список $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n.

Припустимо, Юлія зустрічає Джейн і повертається додому в момент часу $t$ . Юлія буде дотримуватися стратегії, яка мінімізує очікуване значення $t$ . Знайдіть це очікуване значення.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $L$ та $V$ — кількість швидкостей у списку Джейн, довжину вулиці та максимальну швидкість Юлії ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5; $1 \leq L \leq 1 0^{9}$ 1 \le L \le 10^9; $1 \leq V \leq 1 0^{6}$ 1 \le V \le 10^6).

Другий рядок містить $n$ цілих чисел $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n — список можливих швидкостей Джейн у порядку зростання ( $1 \leq v_{1} < v_{2} < \dots < v_{n} \leq 1 0^{6}$ 1 \le v_1 < v_2 < \dotsb < v_n \le 10^6).

Вихідні дані

Виведіть одне дійсне число — очікуваний час, за який Юлія зустріне Джейн і повернеться додому, якщо вона дотримується оптимальної стратегії. Ваша відповідь буде вважатися правильною, якщо її абсолютна або відносна похибка не перевищує $1 0^{- 9}$ 10^{-9}.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі тесту Юлія набагато швидша за Джейн. Найкраще для Юлії рухатися до Джейн якомога швидше, зустріти її в момент часу $25$ на відстані $750$ від дому і повернутися додому в момент часу $50$ .

У другому прикладі тесту Джейн набагато швидша за Юлію. Найкраще для Юлії просто чекати на Джейн вдома, куди Джейн прибуде в момент часу $\frac{1000}{30}$ \frac{1000}{30}.