描述

马里奥有很多银币，有一天他又得到了一张魔法卡，只要使用这张魔法卡，就可以使得他的银币里面所有金额最大的银币都翻倍，所有金额最小的银币都加$1$（也就是银币中金额最大的银币和金额最小的银币都可能不止$1$个），其余的银币的金额不变；马里奥顿时觉得自己要发财了，迫不及待的使用了这张魔法卡，请你求出，马里奥使用了这张魔法卡之后，他的银币的金额分别是多少？ 比如：假设马里奥存有的银币金额分别为$8$$5$$2$$8$$2$$4$，那么使用魔法卡之后，他的银币的金额变为$16$$5$$3$$16$$3$$4$。

输入

第一行是一个整数$n$代表马里奥有$n$个银币（$n \le 1000$） 第二行有$n$个整数，用空格隔开，代表马里奥每个银币的金额。

输出

一行有$n$个整数，用空格隔开，代表使用过魔法卡之后，马里奥的银币的金额，分别是多少？

样例

6
8 2 7 8 2 4

16 3 7 16 3 4