题目内容

小美有一个长度为 $n$ 的数组 $a$，数组中所有元素的值互不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，她会从数组中数值最小的元素的索引开始。每次数数时，她会选择第一个值大于当前位置元素值的元素，直到所有元素都被数过为止。

解题思路

1. 排序映射
   将所有元素与其原始下标组成对 $(a_i, i)$，按照值 $a_i$ 升序排序，得到一组有序对列表 $\text{ord}$。
2. 统计跳转
   从 $\text{ord}[1]$（最小值）开始，每一步跳转都对应相邻两个有序对之间的下标变化：
   • 若 $\text{ord}[k].\text{idx}$ < $\text{ord}[k+1].\text{idx}$，则为正向传送；
   • 否则为逆向传送。
3. 复杂度
   • 排序：$O(n\log n)$