小 Z 是 ZRP（Zombies’ Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近他研究起了诗词音律的问题。在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应 的音符就是这样的：
南 园 满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨
１ １ ５ ５ ６ ６ ５ ４ ４ ３ ３ ２ ２ １
因而可以发现，“1 1 5 5 6 6 5 4 4 3 3 2 2 1” 这串音符就成为了研究音律的关键。
小 Z 翻阅了众多史料发现，过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，将它的音调修改得不下降，
而且使得修改幅度最大的那个音符的修改幅度尽量小。
即如果把一个包含 nnn 个音符的曲子看做是一个正整数数列 A1,…,AnA_1,\ldots,A_nA1,…,An，那么目标是求另一个正整数数列 B1,…,BnB_1,\ldots,B_nB1,…,Bn， 使得对于任意的 1≤i<n1 \leq i < n1≤i<n 有 Bi≤Bi+1B_i \leq B_{i+1}Bi≤Bi+1，而且使得 Ans=max1≤j≤n{∣Aj−Bj∣}\mathrm{Ans}= \max_{1 \leq j \leq n} \{|A_j-B_j|\}Ans=max1≤j≤n{∣Aj−Bj∣} 尽量小。 小 Z 很快就想清楚了做法，但是鉴于他还忙着写诗，
所以这个任务就交给了你。