← 返回题目列表

Codeforces · 1416/A

A. k-惊人的数字

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,由 $$$n$$$ 整数组成,编号从 $$$1$$$ 到 $$$n$$$。

让我们将数组的 $$$k$$$ 惊人数字定义为长度为 $$$k$$$ 的数组的所有子段中出现的最小数字(回想一下,长度为 $$$k$$$ 的 $$$a$$$ 子段是 $$$a$$$ 中恰好包含 $$$k$$$ 元素的连续部分)。如果对于 $$$k$$$ 的某个值,在长度 $$$k$$$ 的所有子段中都没有出现整数,那么 $$$k$$$ 惊人的数字是 $$$-1$$$。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,计算数组 $$$a$$$ 的 $$$k$$$ - 惊人的数字。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 数组中元素的数量。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数,其中第 $$$i$$$ 个整数等于数组中的 $$$i$$$ 惊人数字。

示例

输入 #1

3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1

输出 #1

-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1