Problem description

Wicemaksem ciągu liczbowego o co najmniej dwóch elementach nazywamy wartość jego “drugiego co do wielkości elementu”, a mówiąc precyzyjniej: wicemaksem ciągu jest ta wartość, która znalazłaby się na drugim miejscu po jego nierosnącym uporządkowaniu.

Dla danego ciągu A = A₁, ..., A_N, oblicz średnią arytmetyczną wicemaksów wszystkich spójnych podciągów ciągu A o długości co najmniej 2. Innymi słowy, policz: $$\frac{\sum_{1 \leq i < j \leq N} \mathcal{W}(A_i, \dots, A_j)}{\binom{N}{2}}$$

gdzie 𝒲(A_i,…,A_j) to wicemaks podciągu A_i, …, A_j.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N, oznaczająca długość ciągu. W drugim wierszu znajduje się N liczb całkowitych A₁, ..., A_N, oddzielonych spacjami – są to kolejne elementy ciągu A.

Wyjście

Na wyjściu należy wypisać jedną liczbę, oznaczającą średnią arytmetyczną wicemaksów wszystkich spójnych podciągów ciągu A. Wynik zostanie uznany za poprawny, jeśli jego błąd względny nie będzie większy niż 10⁻⁹.

Ograniczenia

2 ≤ N ≤ 10⁶,  − 10⁹ ≤ A_i ≤ 10⁹.

Podzadania

W testach wartych 20 punktów zachodzi dodatkowo warunek N ≤ 500.

W testach wartych 40 punktów zachodzi dodatkowo warunek N ≤ 5 000.

W testach wartych 80 punktów zachodzi dodatkowo warunek N ≤ 200 000.

Przykład

6
3 9 8 1 2 4

5.26666666666667