#9. 奇怪的序列

奇怪的序列

Description

zty将符合k构造(定义如下)的序列,称为zty-k序列。

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

  • 若n=1,且A1=kA_1=k,则该序列为zty-k序列
  • 若n>1,且A1An2A_1 ~A_{\frac{n}{2}}都为k,An2+1AnA_{\frac{n}{2}+1} ~A_{n}构成zty-(k+1)序列,则该序列为zty-k序列
  • 若n>1,且A1An2A_1 ~A_{\frac{n}{2}}构成zty-(k+1)序列,An2+1AnA_{\frac{n}{2}+1} ~A_{n}都为k,则该序列为zty-k序列

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

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

问最少多少次操作可将序列AA变为zty-1序列?

Format

Input

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

第二行nn个不超过10910^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,2n21062\leq n\leq 2 * 10 ^ 6,且nn为2的整数次幂。