CSES - Inversiot
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Taulukossa on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n ja jokainen luku xix_i on valittu satunnaisesti väliltä 1ri1 \ldots r_i. Luvut on valittu toisistaan riippumattomasti, ja jokaisen välin 1ri1 \ldots r_i luvun todennäköisyys tulla valituksi on sama.

Taulukon inversio on lukupari (a,b)(a,b), jossa a<ba<b ja xa>xbx_a > x_b.

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

Syöte

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

Seuraava rivi sisältää nn kokonaislukua r1,r2,,rnr_1,r_2,\ldots,r_n.

Tuloste

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

Rajat

  • 1n1001 \le n \le 100
  • 1ri1001 \le r_i \le 100

Esimerkki

Syöte:

3
5 2 7

Tuloste:

1.057143