Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Случайный запрос
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a размера n, состоящий из натуральных чисел. Случайно, равновероятно и независимо выбираются два целых числа l и r из отрезка с 1 по n. Если l > r, то значения l и r меняются местами. Найдите матожидание количества различных чисел на подотрезке массива с индекса l по индекс r включительно (в 1-индексации).

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

В первой строке задаётся целое число n (1 ≤ n ≤ 106). Во второй строке заданы n чисел a1, a2, ... an (1 ≤ ai ≤ 106) — элементы массива.

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

Выведите одно число — матожидание количества различных чисел.

Ваш ответ будет засчитан, если его абсолютная или относительная ошибка не будет превосходить 10 - 4 — т. е., формально, если , где x — ответ жюри, а y — ответ, который выдаёт ваша программа.

Примеры
Входные данные
2
1 2
Выходные данные
1.500000
Входные данные
2
2 2
Выходные данные
1.000000