在Internet上的搜索引擎經(jīng)常需要對信息進行比較，比如可以通過某個人對一些事物的排名來估計他（或她）對各種不同信息的興趣，從而實現(xiàn)個性化的服務(wù)。
對于不同的排名結(jié)果可以用逆序來評價它們之間的差異?？紤]1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，滿足j<k,且ij>ik，那么就稱(ij,ik)是這個排列的一個逆序。
一個排列含有逆序的個數(shù)稱為這個排列的逆序數(shù)。例如排列 263451 含有8個逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此該排列的逆序數(shù)就是8。顯然，由1,2,…,n 構(gòu)成的所有n!個排列中，最小的逆序數(shù)是0，對應(yīng)的排列就是1,2,…,n；最大的逆序數(shù)是n(n-1)/2，對應(yīng)的排列就是n,(n-1),…,2,1。逆序數(shù)越大的排列與原始排列的差異度就越大。

現(xiàn)給定1,2,…,n的一個排列，求它的逆序數(shù)。

第一行是一個整數(shù)n，表示該排列有n個數(shù)（n ≤ 100000)。

第二行是n個不同的正整數(shù)，之間以空格隔開，表示該排列。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點擊這里了解課程詳情

信息學(xué)一本通 分治