== include(page="template/taskheader" task_id="mojosort") ==

Poveste şi cerinţă...

Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere *N* banane numerotate cu indici distincţi de la *1* la *N* (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele *1*), până la banana cu indicele *N*.
 
Din păcate, Mojo este mult prea ameţit ca să stea să sorteze banane după bunul plac, motiv pentru care le va mânca în ordinea în care le-a cumpărat. Fiind un geniu în bananologie, Mojo a definit costul unei astfel de permutări ca fiind numărul de inversiuni. Înainte de a se apuca de mâncat, Mojo s-a hotărât să minimizeze numărul de inversiuni ale permutării având la dispoziţie două tipuri de operaţii:
 
* __Monkey Shot__: Mojo alege două elemente consecutive din permutare şi le inversează
* __Monkey Punch__: Mojo dă cu pumnul în masă şi toate bananele se permută random cu probabilitate uniformă (se dă __random shuffle__ la permutare)
 
Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural *K*, Mojo Jojo poate să aplice maxim *K* operaţii descrise mai sus. Calculaţi __expected value__ ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.

h2. Date de intrare