CF1268C K Integers

给定一个排列 $p_1, p_2, \ldots, p_n$。 每次操作，你可以交换两个相邻的数。 你希望通过最少的操作次数，使得排列中存在一个子段 $1,2,\ldots,k$，也就是说，最终存在一个整数 $i$，$1 \leq i \leq n-k+1$，使得 $p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$。 令 $f(k)$ 表示使排列中出现一个值为 $1,2,\ldots,k$ 的子段所需的最小操作次数。 你需要求出 $f(1), f(2), \ldots, f(n)$。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$）：排列的元素个数。 输入的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$：给定的排列（$1 \leq p_i \leq n$）。

输出 $n$ 个整数，依次表示使排列中出现一个值为 $1,2,\ldots,k$ 的子段所需的最小操作次数，$k=1,2,\ldots,n$。

由 ChatGPT 4.1 翻译