UOJ Logo

NOI.AC

1S 512MB

#103. 逆序对

Statistics

题目描述

​ 老虎和蒜头是好朋友。

​ 老虎最近很喜欢研究排列上的问题,例如排列的逆序对问题。不过,老虎向来喜欢反其道而行之,因此他并非已知排列而求逆序对数,而是已知逆序对数求排列。

​ 当然,这个问题对你来说可能太简单了。因此老虎的问题是:给定一个长度为 $ n $ 的排列的所有长度恰好为 $ k $ 的子串的逆序对数,你要求得一个符合条件的原序列。

输入格式

​ 输入的第一行包括两个正整数 $ n, k $ 。

​ 接下来一行包括 $ n - k + 1 $ 个数,其中第 $ i $ 个数表示你所求得的排列 $ p $ 中,子串 $ p[i \ldots i + k - 1] $ 的逆序对数。

输出格式

​ 你只要任意输出一个满足条件的排列 $ p $ 即可。

样例

样例一

input

5 3
2 0 1

output

3 1 2 5 4

数据范围及限制

对于 100% 的数据,$ 2 \le n \le 2 \times 10^5, 2 \le k \le 9, k \le n $ 。

对于 20% 的数据,$ n \le 5 $ ;

对于 40% 的数据,$n \le 1000, k \le 6 $ ;

对于 80% 的数据,$ n \le 2 \times 10^5, k \le 6 $ ;

在以上的每一档数据中均包含 10% 的数据满足 $ k = 2 $ 。

时间限制: 1s

空间限制: 512MB

样例数据下载