题面描述

给定一个长度为$n$的数组$a$下标从$1$开始对于所有$i∈[1,n]∩Z$，求出区间 $[1, i]$ 中第$k$小的数。其中$k$为给定常数。如果区间内的数的数量不足$k$个，请输出$-1$。

思路

1. 使用最大堆 为了高效地求出每个前缀区间 $[1, i]$ 的第 $k$ 小的数，我们可以使用最大堆来动态维护前 $k$ 小的元素。

最大堆：最大堆的特性是堆顶元素是堆中最大的元素。我们通过维护一个大小为 $k$ 的最大堆，可以确保堆中保存的是当前区间的前 $k$ 小的元素，而堆顶即为该区间的第 $k$ 小元素。

题目内容

给定一个长度为 $n$ 的数组 $a$ (下标从 $1$ 开始),对于所有 $i∈[1,n]∩Z$ ，求出区间 $[1,i]$ 中第 $k$ 小的数。其中 $k$ 为给定常数。

输入描述

第一行两个整数 $n,k(1<=k<n<=10^5)$ ,表示数组的长度及两个给定常数。

第二行 $n$ 个整数,第 $2$ 个整数为 $a_i$ 的值($1<=a_i<=n$,且 $a_i$ 互不相等)

输出描述

输出一行 $n$ 个数,第 $1$ 个数为区间 $[1,i]$ 中第 $k$ 小的数,以空格分隔。

若区间内的数的数量不足 $k$ 个,请输出 $-1$ 。

样例1

输入

5 2
5 4 3 2 1

输出

-1 5 4 3 2