Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Inversiot

Inversiot


View task | Model solution | Statistics


Inversiot

Time limit:1.00 s
Memory limit:128 MB

Taulukossa on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$ ja jokainen luku $x_i$ on valittu satunnaisesti väliltä $1 \ldots r_i$. Luvut on valittu toisistaan riippumattomasti, ja jokaisen välin $1 \ldots r_i$ luvun todennäköisyys tulla valituksi on sama.

Taulukon inversio on lukupari $(a,b)$, jossa $a<b$ ja $x_a > x_b$.

Mikä on inversioiden määrän odotusarvo?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: taulukon koko.

Seuraava rivi sisältää $n$ kokonaislukua $r_1,r_2,\ldots,r_n$.

Tuloste

Tulosta odotusarvo pyöristettynä niin, että siinä on tasan 6 desimaalia.

Rajat
Esimerkki

Syöte:
3
5 2 7


Tuloste:
1.057143