题解：AT_abc431_g [ABC431G] One Time Swap 2

前情提要

解题思路

1. $A_l<A_r$ 这会使其字典序变小。$l$ 越小，新序列的字典序越小，对于 $l$ 相等的 $A_r$ 越小字典序越小。
2. $A_l=A_r$ 这不会改变字典序。其数目为 $\sum_{i=1}^{n} \frac{cnt_i(cnt_i-1)}{2}$。
3. $A_l>A_r$ 这会使其字典序变大。$l$ 越小，新序列的字典序越大，对于 $l$ 相等的 $A_r$ 越大字典序越大。