問題文

高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。

• 高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はもちろん 1 である。
• 高橋君以外の社員には、必ず自分より社員番号が小さい上司がただ一人存在する。自分が上司になっている社員のことを、直属の部下と呼ぶ。
• 直属の部下がいない社員の給料は 1 であり、直属の部下がいる社員の給料は 、{\rm max}(その社員の直属の部下の給料) + {\rm min}(その社員の直属の部下の給料) + 1 である。直属の部下が一人しかいない場合は、その部下の給料の 2 倍 + 1 が、その社員の給料となる。

この時、高橋君の給料を求めなさい。

入力例1

5
1
1
1
1

出力例1

3

高橋君は、直属の部下が 4 人いますが、その全ての部下の給料が 1 です。よって、高橋君の給料は、1 + 1 + 1 = 3となります。

入力例2

7
1
1
2
2
3
3

出力例2

7

社員番号 2, 3 の二人の社員が二人部下を持ち、その二人の上司が高橋君、という構成です。 ほかの社員の給料は 1 なので、社員番号 2, 3 の二人の社員の給料は 1 + 1 + 1 = 3 となります。 よって、高橋君の給料は、 3 + 3 + 1 = 7 となります。

入力例3

6
1
2
3
3
2

出力例3

11

高橋君の直属の部下は、社員番号 2 の社員一人だけです。 この社員の直属の部下は、社員番号 3, 6 の二人の社員です。 この二人の給料はそれぞれ 3, 1 なので、社員番号 2 の社員の給料は 5 です。 よって、高橋君の給料は、 5+5+1 = 11 となります。

入力例4

10
1
2
3
4
5
6
7
8
9

出力例4

1023

高橋君の給料は非常に多くなることがあります。