#P15972. [Roi2013 Team]奇特展品(Scanner)

[Roi2013 Team]奇特展品(Scanner)

题目描述

展览上有一件奇特的设备。它会生成一个 11 到 nn 的随机排列,然后扫描该排列,并在屏幕上输出 n−k+1n-k+1 个数。第 ii 个数表示生成排列中区间 [i,i+k−1][i,i+k-1] 的逆序对数量。

逆序对定义为一对下标 (i,j)(i,j),满足 1≤i<j≤n1\le i<j\le n 且 pi>pjp_i>p_j。

设备有两个旋钮,分别控制 nn 和 kk。瓦夏看到了屏幕上的数,想知道设备生成的排列可能是什么。请你输出任意一个符合屏幕显示的排列。

输入格式

第一行包含两个整数 n,kn,k。

第二行包含 n−k+1n-k+1 个整数,表示每个长度为 kk 的连续区间中的逆序对数量。

保证设备正常,并且至少存在一个符合条件的排列。

输出格式

输出 nn 个整数,表示一个符合条件的 11 到 nn 的排列。若有多个答案,输出任意一个。

数据范围

2≤n≤1052\le n\le 10^5,2≤k≤52\le k\le 5,n≥kn\ge k。

样例输入

3 2
0 1

样例输出

1 3 2