给定一个长度为 的整数序列 。 定义序列的一个「峰值」为满足 且 \max(a_{i-1}, a_{i+1})" 的位置 。 每次操作，小苯可以选择一个「峰值」位置 ，然后将 减少 。操作可以进行任意多次。 小苯想知道，通过若干次操作，能够得到的字典序最小的序列是什么。 【名词解释】 序列的字典序比较：从左到右逐个比较两个序列的元素。如果在某个位置上元素不同，比较这两个元素的大小，元素小的序列字典序也小。如果一直比较到其中一个序列结束，则长度较短的序列字典序更小。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入一个整数 ，表示序列的长度。 第二行输入 个整数 ，表示序列中的各个元素。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

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