#LAISIR19. 叛逆的隊伍

叛逆的隊伍

🧮 題目名稱:叛逆的隊伍

📝 題目描述:

在某個訓練有素的軍營中,士兵們正準備出發執行任務。他們排成了一列長隊,每個士兵都有一個戰鬥力指數 aia_i

根據指揮官的要求,隊伍必須從前到後按非遞減順序排列才能維持最佳作戰效率。然而,這支隊伍卻出現了不少「叛逆組合」:也就是站在前面的士兵比站在後面的士兵戰鬥力還要強,這可能造成混亂和指令延誤。

為了評估隊伍混亂程度,指揮官希望你幫他統計這支隊伍中共有多少對「叛逆組合」。形式化來說,請計算有多少對 (i,j)(i, j) 滿足:

  • 1i<jn1 \leq i < j \leq n
  • ai>aja_i > a_j

📥 輸入格式:

輸入包含兩行。

第一行為一個整數 nn,表示士兵的人數。

第二行包含 nn 個整數 a1,a2,,ana_1, a_2, \ldots, a_n,代表每位士兵的戰鬥力指數。


📤 輸出格式:

輸出一行,一個整數,表示「叛逆組合」的總數量。


📘 範例輸入:

5
2 4 1 3 5

📗 範例輸出:

3

範例說明:這支隊伍中有三對「叛逆組合」:

  • 士兵 1 和 3(2 > 1)
  • 士兵 2 和 3(4 > 1)
  • 士兵 2 和 4(4 > 3)

📊 數據範圍與限制:

  • 1n1051 \leq n \leq 10^5
  • 109ai109-10^9 \leq a_i \leq 10^9
  • 數列中元素可重複