D. Протест Джерри
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эндрю и Джерри играют в игру, а Гарри ведёт счёт. Игра состоит из трёх раундов. В каждом раунде Эндрю и Джерри по очереди вынимают по одному шару из урны, содержащей n шаров, на которых написаны различные целые числа. Затем они передают шары Гарри, который добавляет очко тому, на чьём шаре было написано большее число, и кладёт их обратно в урну. Победителем игры объявляется тот, кто выиграл хотя бы в двух раундах из трёх.

Известно, что Эндрю выиграл в раундах 1 и 2, а Джерри победил в раунде 3, так что победителем игры стал Эндрю. Однако Джерри недоволен способом определения победителя — по его словам, сумма чисел на вытянутых им шарах была строго больше суммы чисел на шарах, вытянутых Эндрю. Какова вероятность такого события?

Входные данные

В первой строке входных данных записано единственное число n (2 ≤ n ≤ 2000) — количество шаров в урне.

Во второй строке записаны n целых чисел ai (1 ≤ ai ≤ 5000) — числа, написанные на шарах. Гарантируется, что все ai различны.

Выходные данные

Выведите единственное вещественное число — вероятность того, что сумма чисел на всех шарах, вытянутых Джерри, была строго больше суммы чисел на всех шарах, вытянутых Эндрю, если известно, что Эндрю выиграл первые два раунда, а Джерри выиграл третий раунд. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не будет превосходить 10 - 6.

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
2
1 2
Выходные данные
0.0000000000
Входные данные
3
1 2 10
Выходные данные
0.0740740741
Примечание

В первом примере имеется всего два шара. В первых двух раундах Эндрю обязательно доставал шар с числом 2, а Джерри доставал шар с числом 1, и наоборот в последнем раунде. Таким образом, сумма на всех шарах Эндрю обязательно равна 5, а на всех шарах Джерри — 4.

Во втором примере у каждой игры могло быть три исхода: 10 - 2, 10 - 1 или 2 - 1. Чтобы выполнилось условие на сумму, Эндрю обязательно должен был оба раза победить с исходом 2 - 1, а в последнем раунде Джерри должен был достать 10. Вероятность такого события равняется .