Ինվերսիաների քանակ (Inversion Count)
Երբեմն, հեռավոր ու առեղծվածային երկրում ապրում էր իմաստուն կախարդ Մերլին անունով։ Նա ուներ բացառիկ կարողություն՝ ճանաչելու համակցված պատկերները թողարկումներում (permutations)։ Մերլինին հատկապես հետաքրքրում էր «ինվերսիա» (inversion) երևույթը թողարկման մեջ:
Թողարկման (permutation) ինվերսիա է համարվում զույգ տարրեր
($a_i, a_j$) այն պայմանով, որ i < j և $a_i > a_j$։ Թողարկման մեջ ինվերսիաների քանակը ցույց է տալիս, թե որքանով է տվյալ շարքը հեռու աճումը պարզ (ascending order) կերպով սորտավորված լինելուց։Մերլինը որոշեց առաջադրանք տալ շնորհալի ծրագրավորողներին. առաջարկեց հետևյալ խնդիրը. եթե տրված է 1-ից մինչև n ամբողջ թվերի թողարկում, անհրաժեշտ է գտնել, թե քանի ինվերսիա ունի այդ թողարկումը։
Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ 100 000), որը ցույց է տալիս թողարկման չափը։ Երկրորդ տողում տրված են n ամբողջ թվեր, որոնք բաժանված են բացատներով և ներկայացնում են թողարկման տարրերը։Ելք
Պետք է տպել մեկ ամբողջ թիվ, який ցույց է տալիս թողարկման մեջ եղած ինվերսիաների քանակը։
Օրինակներ
Մուտք | Ելք |
5
3 1 4 2 5 | 3 |
4
1 2 3 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB