B-小苯的峰值序列_牛客周赛 Round 125

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 定义序列的一个「峰值」为满足 $1 < i < n$ 且 $a_i > \max(a_{i-1}, a_{i+1})$ 的位置 $i$ 。

$\hspace{15pt}$ 每次操作，小苯可以选择一个「峰值」位置 $i$ ，然后将 $a_i$ 减少 $1$ 。操作可以进行任意多次。
$\hspace{15pt}$ 小苯想知道，通过若干次操作，能够得到的字典序最小的序列是什么。

【名词解释】
$\hspace{15pt}$ 序列的字典序比较：从左到右逐个比较两个序列的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素小的序列字典序也小。如果一直比较到其中一个序列结束，则长度较短的序列字典序更小。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示序列的长度。 
第二行输入  个整数 ，表示序列中的各个元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出  个整数，表示能够得到的字典序最小的序列。

示例1

输入

复制

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

输出

复制

3 1 1 1 5
2 2 1 2 2 3
1 1

说明

对于第一组测试数据，序列的「峰值」有且仅有 ，连续对  进行三次操作即可得到字典序最小的序列。