Description

zty将符合k构造（定义如下）的序列，称为zty-k序列。

对于一个长度为n（n为2的整数次幂）的序列A，若其能成为zty-k序列，则符合以下条件中的一个：

• 若n=1，且$A_1=k$，则该序列为zty-k序列
• 若n>1，且$A_1 ～A_{\frac{n}{2}}$都为k，$A_{\frac{n}{2}+1} ～A_{n}$构成zty-(k+1)序列，则该序列为zty-k序列
• 若n>1，且$A_1 ～A_{\frac{n}{2}}$构成zty-(k+1)序列，$A_{\frac{n}{2}+1} ～A_{n}$都为k，则该序列为zty-k序列

例如：[2]、[2,3]、[3,2]、[2,2,3,4]、[3,4,2,2]为zty-2序列

给定序列$A$，每次操作可将其中一个位置的数字变为任意值。

问最少多少次操作可将序列$A$变为zty-1序列？

Format

Input

第一行一个正整数$n(n\leq 2*10^6, \exists k(n = 2^k))$，代表数字个数

第二行$n$个不超过$10^9$的正整数，代表该序列

Output

第一行一个正整数，代表将原序列改造为zty-1序列，最少的操作次数

第二行输出该序列改造后的zty-1序列，若有多个符合条件的解，请输出字典序最小的一组。

Samples

8
2 2 3 4 1 1 1 1

0
2 2 3 4 1 1 1 1

32
8 10 14 19 11 13 5 19 4 10 1 6 13 3 8 4 8 10 1 13 4 10 10 18 1 14 20 19 17 16 18 7

27
2 2 2 2 2 2 2 2 4 4 5 6 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Limitation

本题共有10个测试点，每个测试点10分。

对于测试点1-2，n = 2

对于测试点3，n = 32，且序列全为1

对于测试点4-5，n = 32

对于测试点6-10，$2\leq n\leq 2 * 10 ^ 6$，且$n$为2的整数次幂。