T643058 [CS-M5-J] 逆袭

选举往往充满了不可预测的反转。一场选举，尤其是激烈的总统选举，可能从一开始就充满了逆转的戏剧性——有时看似稳操胜券的候选人，可能会在关键时刻被意想不到的对手反超。例如在自由国总统选举中，建国与哈哈姐的选战就经历了诸多戏剧性的逆转。建国在选举初期得到了大量支持，但随着选民的态度转变，哈哈姐的支持率不断攀升，就在大家以为哈哈姐要获胜的时候，誰也没想到建国在最后发力了赢得人心，同时有最强辅助钢铁侠的帮助，最终实现了“逆袭”，成功赢得了总统选举的胜利。 这场选举的进程充满了“逆序对”——每一次投票的变化，每一次数据的更新，似乎都能带来新的反转。政治选举本身就像一个数组，每一位选民的选择代表了数组中的元素，而这些元素的“逆序对”可能决定最终的胜者。 现在，你也将面对一个类似的挑战：在给定的数组中，找出那些看似逆转的“逆序对”。你的任务是计算数组中，哪些元素违反了本该遵循的顺序，就像选举中的那一次次反转，揭示出潜在的“逆袭”。

给定一个长度为 $n$ 的数组，求这个数组中逆序对的个数。 **逆序对:** 对于数组中两个元素 $a_i,a_j$，如果 $i \lt j$ 并且 $a_i\gt a_j$，则说明这是一对逆序对。

第一行输入一个正整数 $n$，表示数组长度。 第二行输入 $n$ 个正整数，表示数组对应位置的元素。

输出一个整数，表示答案

【数据范围】 对于前 $25\%$ 的数据，保证 $1\le n\le 10^3,1\le a_i\le 10^4$。 对于 $100\%$ 的数据，保证 $1\le n\le 10^5,1\le a_i\le 10^9$。