Problem description
Jasio dostał od rodziców na urodziny nowiutki, markowy, pachnący jeszcze fabryką ciąg liczb całkowitych a1, …, aN. Jasio od razu przystąpił do zabawy ciągiem: wybiera losowo fragment (spójny niepusty podciąg) ai, ai + 1, …, aj i wyznacza minimum tego podciągu. Jasio wybiera jednorodnie: wybór każdego podciągu ai, ai + 1, …, aj dla pary indeksów i, j spełniających warunek 1 ≤ i ≤ j ≤ N jest jednakowo prawdopodobny. Niestety, Jasio jest dość depresyjnym dzieckiem: po obejrzeniu ciągu Jasio popada w dziecięcą depresję i rodzice muszą go pocieszać przez m sekund, gdzie m to minimum wybranego przez niego podciągu.
Rodzice Jasia chcą przewidzieć, ile czasu będą musieli poświęcić na pocieszanie Jasia. Pomóż im i napisz program, który: wczyta ciąg liczb, który otrzymał Jasio, wyznaczy i wypisze oczekiwany czas depresji Jasia.
Wejście
W pierwszym wierszu wejścia znajduje się liczba naturalna N, określająca długość ciągu, który dostał Jasio. W drugim wierszu wejścia znajduje się opis ciągu, który dostał Jasio; jest to N liczb naturalnych a1, …, aN pooddzielanych pojedynczymi odstępami.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba rzeczywista: oczekiwana wartość czasu m, przez który rodzice będą musieli pocieszać Jasia.
Odpowiedź uznaje się za prawidłową, jeśli błąd względny lub bezwzględny obliczonej wartości nie przekracza 10−6.
Ograniczenia
1 ≤ N ≤ 1 000 000, 1 ≤ ai ≤ 1 000 000.
Przykład
| Input | Output | Explanation |
|
|
W tym przykładzie jest 6 możliwych podciągów, (1), (7), (2), (1,7), (7,2), (1,7,2), dla których trzeba będzie pocieszać Jasia przez odpowiednio: 1, 7, 2, 1, 2, 1 sekund. Średni czas pocieszania Jasia to $2\frac{1}{3}$ sekundy. |
Przykład
| Input | Output | Explanation |
|
|
W tym przykładzie jest 15 możliwych podciągów. Dla dwunastu z nich trzeba pocieszać Jasia przez 2 sekundy, dla trzech przez 3 – są to podciągi (3), (3), (3,3). Średni czas pocieszania Jasia to $2\frac{1}{5}$ sekundy. |