AT_arc031_3.[ARC031C] 積み木

有 $N$ 个高度各不相同的积木排成一行。你可以多次交换相邻的两个积木。请计算，最少需要多少次交换，才能使积木从最高的那个开始，向左右两边高度依次递减。也就是说，设重新排列后第 $i$ 个积木的高度为 $A_i$，最高的积木的位置为 $T$，则需要满足：

• $A_1 < A_2 < \cdots < A_T > \cdots > A_{N-1} > A_N$

请输出完成这种排列所需的最小交换次数。

输入通过标准输入给出，格式如下：

$N$ $B_1$ $B_2$ ... $B_N$

• 第 $1$ 行给出积木的数量 $N\ (1 \leq N \leq 10^5)$。
• 第 $2$ 行给出初始排列下每个积木的高度 $B_i\ (1 \leq B_i \leq N)$。
• 所有积木高度均不相同，即 $B_i \neq B_j\ (i \neq j)$。

输出完成排列所需的最小交换次数。输出末尾需换行。

部分分

本题有 $2$ 个数据集，每个数据集有不同的部分分。

• 对于满足 $N \leq 100$ 的数据集 $1$，答对可得 $30$ 分。
• 对于无额外限制的数据集 $2$，答对可得 $70$ 分（与上面数据集分数无关）。

由 ChatGPT 4.1 翻译