#[. [RC-05] 排列

Type: RemoteJudge

4000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

给出 $1\sim n$ 的排列 $p$ ，下标从 $1$ 开始。

恰好 $K$ 次任意选择 $1\le i<n$ 并交换 $p_i,p_{i+1}$ 。问交换完毕后，字典序最小的排列 $p$ 是什么？

第一行两个非负整数 $n,K$ ，分别表示排列中数的个数和交换次数。

接下来一行 $n$ 个整数，描述排列 $p$ 。

一行以空格隔开的 $n$ 个正整数，描述交换完成之后的排列。

5 2
2 1 4 3 5

1 2 3 4 5

5 3
5 4 3 2 1

2 5 4 3 1

5 6
5 4 3 2 1

1 3 5 4 2

本题捆绑测试。

对于所有数据， $1\le n\le 5\times 10^5$ ， $0\le K\le 10^{12}$ 。

详细数据范围如下表：

Subtask 编号	$n$	$K$	分数
$1$	$\le 8$		$30$
$2$	$\le 10^3$		$30$
$3$	$\le 10^3$	$=10^{12}$	$15$
$4$	$\le 5\times 10^5$		$25$