問題
背景
鳗鱼王国的公主热爱数据结构。所以国王准备在她生日送她许多“代表二进制堆的数组”。
“表示二元堆的数组”指的是 i 元素的值为2i+1如果某个元素存在,则该元素严格小于它,同样,如果第2i+2个元素存在,则它严格小于它,这个条件在所有元素中都满足的数组被称为二叉堆。比如 [0,1,4,2,3] 是表示二叉堆的数组。因为第0个元素0比第1个元素和第2个元素1和 按字典顺序比较4更小,比第1个元素1比第3个元素和第4个元素的2和 按字典顺序比较3也更小……这样的条件全部成立。这样的数组可以被看作是一种树结构,其中第i个元素的子节点是第2i+1个元素和第2i+2个元素,并且具有父节点的值始终较小的特征。公主沉迷于利用这一特征来提高排序等各种算法的效率。
然而,不幸的是,国王把好不容易做好的“表示二叉堆的数组”掉落并弄坏了!现在国王手里只剩下了“表示二叉堆的数组”的后半部分。必须尽快恢复原来的“表示二叉堆的数组”。国王记得,原数组的元素都是非负整数,并且没有重复值。希望你能利用这些信息来恢复数组。
課題
换句话说,对于输入 A0 ... AN-1 , H0 ... HM-1 要求找到满足以下条件的数组 M 并将其长度作为答案输出。
- Hi 就是全部 0 的整数
- 数组的所有元素都是互不相同的。也就是说,i \neq j 如果 Hi \neq Hj
- 它是表示二叉堆的数组。也就是说,它始终 Hi \lt H2i+1 和 Hi \lt H2i+2
- A 是 在 H 是其后缀。也就是说,对于所有 0 \leq k \lt N , 定义Ak = HM-N+k
存在多种可能的情况时,取最小的。 M 。满足条件的 H 不存在,则 -1 回答。
配点
100
入力
输入按以下格式给出。
N A0 A1 ... AN-1
制約
输入中的每个变量都满足以下约束。
- 1 \leq N \leq 100
- 0 \leq Ai \leq 109
- Ai 是彼此不同的非负整数
出力
问题的解决办法 在1行输出。 没有
入力例1
3 4 2 3
输入示例 1 的输出示例 路径
5
[4,2,3] 是4(第0个,比2呀 请注意,它可能是3(第1,第2个元素要大,因此不满足条件。[*,4,2,3] 形式的数组也因为大于4(第1个,比3(第3 = 2 \times 1+1个元素,所以无论*填入什么值都不满足条件。它是以[0,1,4,2,3] 是, 当[4,2,3] 作为后缀表示二叉堆的最短数组。注意,
入力例2
3 3 1 2
输入示例 2 的输出示例
-1
[0,1,3,1,2] 呀 请注意,它可能是 [-1,0,3,1,2] 由于数组元素没有重复且为非负整数等原因,不满足条件。
入力例3
4 10 20 40 30
输入示例 3 的输出示例
4
入力例4
4 9 2 3 6
输入示例 4 的输出示例
8