東京大学プログラミングコンテスト2013

D - 壊れかけのヒープ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

背景

うなぎ王国のお姫様は,データ構造が大好きだ.そこで王様は,お姫様の誕生日に「バイナリヒープを表現した配列」をたくさんプレゼントしようと準備していた.

「バイナリヒープを表現した配列」とは,配列の第 i 要素の値は,第2i+1要素が存在すればそれより真に小さく,同様に第2i+2要素が存在すればそれよりも真に小さい,という条件を全ての要素で満たす配列のことを言う.たとえば [0,1,4,2,3] はバイナリヒープを表現した配列である.なぜならば,第0要素である0は第1要素と第2要素である14よりも小さく,第1要素である1は第3要素と第4要素の23よりも小さい…,という条件がすべて成り立っている.このような配列は,第i要素の子が第2i+1要素と第2i+2要素であるようなツリー構造と考えると,親の方が常に値が小さいという特徴を持つ.お姫様は,この特徴を活用してソートなど様々なアルゴリズムの効率化をするのにご執心なのだ.

「バイナリヒープを表現した配列」の例
1: 「バイナリヒープを表現した配列」の例

さて,ところが不運なことに,王様はせっかく作った「バイナリヒープを表現した配列」を落として壊してしまった!今や王様の手元には,「バイナリヒープを表現した配列」の後半部分しか手元に残っていない.一刻も早く元の「バイナリヒープを表現した配列」を復元しなくてはならない.王様は,元の配列の要素はすべて非負整数で,重複する値はなかったことを覚えている.この情報を手がかりに配列を復元して欲しい.

課題

すなわち,入力 A0 ... AN-1 に対し,次を満たす配列 H0 ... HM-1 を求め,その長さ M を答えとして出力して欲しい.

複数の可能性がある場合は最小の M を答えること.条件を満たす H が存在しない場合は -1 と答えること.

配点

100

入力

入力は以下の形式で与えられる.

N
A0 A1 ... AN-1

制約

入力中の各変数は以下の制約を満たす.

出力

問題の解を1行に出力せよ.

入力例1

3
4 2 3

入力例1に対する出力例

5

[4,2,3] は,4(第0要素)が23(第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

Submit提出する