期末考试结束了。

现在到了即将出成绩的时候，但是所有的期末成绩突然丢失了，现在只有根据每个人的平时成绩，为了让大家及时得到成绩，只能临时拼凑一份成绩单。

一共有 $n$ 名同学的成绩丢失了，但是知道每个人的平时成绩 $a_i$，现在要求给每个人赋一个期末成绩，使得期末成绩序列 ${b_n}$ 满足以下条件

• 为了公平，对于相邻的同学，平时成绩高的期末成绩也高，若两人平时成绩相等，则期末成绩相等
• 由于某些不可知的原因，出题人希望总的期末成绩最低
• 考虑同学们的心情，要保证成绩为正数，即 $b_i>0$

第 $i$ 个同学和第 $j$ 个同学相邻当且仅当 $|i-j|=1$

输入的第一行为一个整数 $\ (3 \leq n\leq 10^6)$ 表示同学的数量。

接下来的一行有 $n$ 个整数，表示每个同学的平时成绩 $a_i\ (1\leq a_i \leq 10^9)$。

请输出一行，包含 $n$ 个正整数，相邻整数之间以单个空格分隔，每个整数 $b_i$ 表示每个人的期末成绩 。