说明

徐老师最近在玩一个房屋建造类游戏，现在他已经造好了自己的房子，于是他决定买一些家具来装饰自己的房子

徐老师的房子里有一面装饰墙，这面装饰墙上一共有 $n$ 个架子，每个架子上已经由系统自动生成了一个摆件

徐老师发现这个装饰系统做的相当粗糙，居然总共只有 $26$ 种不同的摆件，这让装饰的可能性大大降低了！

于是徐老师降低了对装饰的要求，他现在只想把这个装饰墙摆成从中间看左右对称的样子

即第 $1$ 个摆件和第 $n$ 个摆件相同，第 $2$ 个摆件和第 $n - 1$ 个摆件相同

但是徐老师的钱都已经拿来造房子了，他没有那么多的预算能够买很多摆件

所以他决定最多只选择两个摆件，将它们分别替换成任意一个款式的摆件

现在请你徐老师计算一下，他应该如何替换摆件？如果存在多组方案，请输出字典序最小的那一组

P.S. $[1,2,3,2,1]$ 和 $[1,2,1]$ 都是满足要求的摆放方案，而 $[1,2,3]$ 则不是

输入格式

第一行一个正整数 $n$，表示有 $n$ 个摆件

接下来一行 $n$ 个整数分别表示从左往右每一个摆件的款式 $a_i$

|  数据点编号   | $n$的范围 |
|  :----:  | :----:  | 
| $1 \sim 2$  | $1\leq n \leq 10$ | 
| $3 \sim 5$  | $1\leq n \leq 1000$ | 
| $6 \sim 10$ | $1\leq n \leq 100000$ | 

特别的保证：$1 \leq a_i \leq 26$，保证至少存在一组方案

输出格式

输出一行包含 n 个整数，表示替换摆件后从左往右每一个摆件的款式

样例

5
1 2 3 4 5

1 2 3 2 1