Codeforces Round 198 (Div. 2) |
---|
Закончено |
Яхуб — ярый поклонник туристов. Он и сам хочет стать туристом и поэтому запланировал поездку. На прямой дороге расположены n пунктов назначения, Яхуб хочет посетить их все. Он начинает экскурсию с километра номер 0. Яхубу известно как расположены пункты назначения на дороге. Он знает последовательность целых чисел a1, a2, ..., an, в которой число ak обозначает, что k-тый пункт назначения находится на расстоянии ak километров от точки начала экскурсии. Известно, что никакие два пункта не расположены в одном и том же месте.
Яхуб хочет посетить каждый пункт ровно один раз. Обратите внимание, что если Яхуб пересекает какой-то пункт назначения по дороге к другому пункту, это не считается посещением. То есть, если Яхуб двигается к какому-то пункту, чтобы посетить его, и по дороге встречает непосещенный пункт, такое событие не считается посещением пункта. Также, после того как Яхуб посетит свой последний пункт назначения, он не возвращается на километр 0, то есть в последнем пункте путешествие заканчивается.
Расстояние между пунктом, находящемся на километре x, и следующим пунктом, находящемся на километре y, считается равным |x - y| километров. «Путем» называется порядок прохождения пунктов назначения. Яхуб может посещать пункты в том порядке, в каком хочет, лишь бы он посетил все n пунктов назначения и при этом не посетил никакой пункт более одного раза.
Яхуб начинает выписывать на бумаге все возможные пути. Для каждого пути он отмечает расстояние, которое надо будет пройти, если следовать этому пути. Яхуб хочет найти среднее количество километров в пути. Ему уже наскучило выписывать все пути, поэтому он просит Вас помочь ему.
В первой строке записано целое число n (2 ≤ n ≤ 105). В следующей строке записаны n различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ 107).
Выведите два целых числа — числитель и знаменатель дроби, равной требуемому среднему значению. Дробь должна быть несократимая.
3
2 3 5
22 3
Рассмотрим 6 возможных путей:
Таким образом средняя длина пути в километрах = = .
Название |
---|