题目描述

给定一个序列 $a_i$（$1\leq a_i\leq 10^9$）且 $1\leq i\le n$ 且 $n\leq 1.5\times 10^7$，和一个整数 $k$（$k\leq n$ 且 $k\leq 10^6$），求出 $a$ 的一个长度为 $k$ 的子序列 $a_{b_i}$ 满足：

1. $1\leq b_1\leq b_2\leq \ldots\leq b_k$
2. 在满足 $1$ 的情况下 $a_{b_1}, a_{b_2},\ldots , a_{b_k}$ 字典序最大。

输入格式

第一行一个数 $k$，以下一行，为序列 $a_i$。以一个单独的 $0$ 结束。

输出格式

$k$ 行，每行一个数，其中第 $i$ 行为 $a_{b_i}$。

3
12 5 8 3 15 8 0

12
15
8

提示

本题原为交互题，为了正常评测，你需要下载后解压，并把etap2/arc/prog里的carclib.c贴到程序之前。

评测方式

首先请按 说明/提示 中说的做

然后将 #include "carclib.h" 去掉

将第一次输入改为 =inicjuj() 形式，将之后的每一次输入改为 =wczytaj() 形式，将输出改为 wypisz(jakoscProjektu) 形式（jakoscProjektu 代表你输出的数）

最后切记不能开O2