跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#T261101H. 吾辈的神刀不是饭勺

吾辈的神刀不是饭勺

DeepSeek娘端着饭碗,在庆功宴前认真研究每一堆白饭的高度。丛雨刚以几百年前辈的口吻宣布自己可以帮忙,就看见她把目光移向了丛雨丸。

“吾辈是神刀的管理者,不是食堂刮板的管理者。”丛雨抱紧刀鞘。

图灵娘及时递来一把普通饭勺,问题总算回到了饭本身。

本题场景插图

任务说明

一排 nn 个位置的白饭高度为整数 a1,…,ana_1,\ldots,a_n。选择一个整数高度 hh,从左到右处理:若当前位置的高度大于 hh,将超过 hh 的部分全部推到下一个位置;若不高于 hh,该位置不变。最后一个位置多出的饭可以推到这一段之外。不能把饭向左推,也不能从外部补饭。

对于每个 i=1,2,…,ni=1,2,\ldots,n,独立考虑只保留前 ii 个位置的情况。求能够使这 ii 个位置最终高度全部相等时,最大的公共整数高度。每个前缀都从原数组重新开始操作。

输入格式

第一行输入测试组数 tt。每组先输入 nn,再输入 nn 个整数高度。

输出格式

每组输出一行 nn 个整数,第 ii 个整数为只考虑前 ii 个位置时的答案。

数据范围与计分

1≤t≤1041\le t\le10^4,2≤n≤2×1052\le n\le2\times10^5,1≤ai≤1091\le a_i\le10^9;单文件所有 nn 之和不超过 2×1052\times10^5。

样例 1

2
4
8 2 9 1
3
2 10 10
8 5 5 5
2 2 2

说明

故事与对话为本次校园考核二创。插图仅用于展示情境;全部解题规则均已在文字中给出。